Универсальная вершина
В теории графов универсальной вершиной называется вершина неориентированного графа , смежная со всеми остальными вершинами графа. Ее также можно назвать доминирующей вершиной , так как она образует одноэлементное доминирующее множество в графе. (Его не следует путать с универсальной кванторной вершиной в логике графов .)
Граф, содержащий универсальную вершину, можно назвать конусом . В этом контексте универсальную вершину также можно назвать вершиной конуса. [1] Однако эта терминология противоречит терминологии вершинных графов , в которой вершина — это вершина, удаление которой оставляет планарный подграф.
Звезды — это в точности деревья , имеющие универсальную вершину, и их можно построить, добавив универсальную вершину в независимый набор . Колесные графы также могут быть образованы добавлением универсальной вершины к циклическому графу . [2] В геометрии трехмерные пирамиды имеют графы колес в качестве скелетов , и, в более общем смысле, граф любой многомерной пирамиды имеет универсальную вершину в качестве вершины пирамиды.
Тривиально совершенные графы ( графы сравнимости порядково - теоретических деревьев ) всегда содержат универсальную вершину, корень дерева, и более строго их можно охарактеризовать как графы, в которых каждый связный индуцированный подграф содержит универсальную вершину. [3] Связные пороговые графы образуют подкласс тривиально совершенных графов, поэтому они также содержат универсальную вершину; их можно определить как графы, которые могут быть образованы повторным добавлением либо универсальной вершины, либо изолированной вершины (без инцидентных ребер). [4]
Каждый граф с универсальной вершиной является разборным графом , что означает, что его можно свести к одной вершине, многократно удаляя вершины, замкнутые окрестности которых являются подмножествами замкнутых окрестностей других вершин. Под это определение подходит любая последовательность удаления, которая оставляет универсальную вершину на месте, удаляя все остальные вершины. Почти все разборные графы имеют универсальную вершину в том смысле, что доля -вершинных разборных графов, имеющих универсальную вершину, стремится к единице в пределе при стремлении к бесконечности. [5]
В качестве частного случая наблюдения, что число доминирования увеличивается не более чем мультипликативно в сильных произведениях графов , [6] сильное произведение имеет универсальную вершину тогда и только тогда, когда оба его множителя имеют универсальную вершину.
