Универсальная вершина - Universal vertex

В теория графов, а универсальная вершина это вершина из неориентированный граф смежный со всеми остальными вершинами графа. Его также можно назвать доминирующая вершина, поскольку он образует одноэлементный доминирующий набор в графике. (Не следует путать с универсально определяемый вершина в логика графиков.)

Граф, содержащий универсальную вершину, можно назвать конус. В этом контексте универсальную вершину можно также назвать вершина конуса.[1] Однако эта терминология противоречит терминологии графики вершин, в котором вершина - это вершина, удаление которой оставляет плоский подграф.

В специальных семействах графов

В звезды точно деревья которые имеют универсальную вершину, и могут быть построены путем добавления универсальной вершины к независимый набор. В колесные графики аналогично может быть образована добавлением универсальной вершины к график цикла.[2] В геометрии трехмерное пирамиды имеют колесные графики в качестве своих скелеты, и в более общем плане граф любой многомерной пирамиды имеет универсальную вершину в качестве вершина пирамиды.

В тривиально совершенные графы (в графики сопоставимости из теоретико-порядковые деревья ) всегда содержат универсальную вершину, корень дерева, и, что более важно, их можно охарактеризовать как графы, в которых каждая связная индуцированный подграф содержит универсальную вершину.[3]Связанный графики пороговых значений образуют подкласс тривиально совершенных графов, поэтому они также содержат универсальную вершину; их можно определить как графы, которые могут быть сформированы путем повторного добавления либо универсальной вершины, либо изолированной вершины (той, которая не имеет инцидентных ребер).[4]

Каждый граф с универсальной вершиной является разборный граф, и почти все демонтируемые графы имеют универсальную вершину.[5]

Другие свойства

На графике с п вершин универсальной вершиной называется вершина, степень точно п − 1. Поэтому, как и разделить графики, графы с универсальной вершиной можно распознать только по их последовательности степеней, не глядя на структуру графика.

Рекомендации

  1. ^ Ларрион, Ф .; de Mello, C.P .; Morgana, A .; Нойман-Лара, В.; Писанья, М. А. (2004), "Оператор клики на кографах и последовательных графах", Дискретная математика, 282 (1–3): 183–191, Дои:10.1016 / j.disc.2003.10.023, МИСТЕР  2059518.
  2. ^ Бонато, Энтони (2008), Курс по веб-графику, Аспирантура по математике, 89, Атлантическая ассоциация исследований в области математических наук (AARMS), Галифакс, штат Нью-Йорк, с. 7, Дои:10,1090 / г / м2 / 089, ISBN  978-0-8218-4467-0, МИСТЕР  2389013.
  3. ^ Волк, Э. С. (1962), "Граф сравнимости дерева", Труды Американского математического общества, 13: 789–795, Дои:10.2307/2034179, МИСТЕР  0172273.
  4. ^ Хваталь, Вацлав; Хаммер, Питер Лэдислав (1977), «Агрегация неравенств в целочисленном программировании», в Hammer, P.L .; Johnson, E. L .; Korte, B.H .; Немхаузер, Г. Л. (ред.), Исследования в области целочисленного программирования (Proc. Worksh. Bonn, 1975), Анналы дискретной математики, 1, Амстердам: Северная Голландия, стр. 145–162..
  5. ^ Бонато, Энтони; Кемкес, Грэм; Prałat, Paweł (2012), «Почти все графы Cop-win содержат универсальную вершину», Дискретная математика, 312 (10): 1652–1657, Дои:10.1016 / j.disc.2012.02.018, МИСТЕР  2901161.

внешняя ссылка