В теории графов , универсальная вершина является вершиной из неориентированного графа , которая смежна со всеми остальными вершинами графа. Ее также можно назвать доминирующей вершиной , поскольку она образует одноэлементное доминирующее множество в графе. (Не следует путать с универсально определенной квантовой вершиной в логике графов .)
Граф, содержащий универсальную вершину, можно назвать конусом . В этом контексте универсальную вершину можно также назвать вершиной конуса. [1] Однако эта терминология противоречит терминологии графов вершин , в которых вершина - это вершина, удаление которой оставляет плоский подграф.
В специальных семействах графов
В звезды в точности дерева , которые имеют универсальную вершину, и может быть построена путем добавления универсальной вершины к независимому набору . Эти колеса графики , подобным образом , может быть сформирован путем добавления универсальной вершины в графе цикла . [2] В геометрии трехмерные пирамиды имеют графы-колеса в качестве скелетов , и, в более общем смысле, граф любой многомерной пирамиды имеет универсальную вершину в качестве вершины пирамиды.
В тривиальном совершенных графах (то сравнимость графика из порядка теоретико-дерев ) всегда содержат универсальную вершину, корень дерева, и более сильно они могут быть охарактеризованы в виде графиков , в котором каждый соединен подграф содержит универсальную вершину. [3] Связные пороговые графы образуют подкласс тривиально совершенных графов, поэтому они также содержат универсальную вершину; их можно определить как графы, которые могут быть сформированы путем повторного добавления либо универсальной вершины, либо изолированной вершины (той, которая не имеет инцидентных ребер). [4]
Каждый граф с универсальной вершиной является демонтируемым графом , и почти все демонтируемые графы имеют универсальную вершину. [5]
Прочие свойства
В графе с n вершинами универсальной вершиной называется вершина, степень которой равна точно n - 1 . Следовательно, как и расщепленные графы , графы с универсальной вершиной можно распознать исключительно по их последовательностям степеней , не глядя на структуру графа.
Рекомендации
- ^ Ларрион, Ф .; де Мелло, КП; Morgana, A .; Нойман-Лара, В .; Pizaña, М. (2004), "Клика оператор на cographs и последовательных граф", дискретная математика , 282 (1-3): 183-191, DOI : 10.1016 / j.disc.2003.10.023 , МР 2059518.
- ^ Бонато, Энтони (2008), Курс по веб-графу , Аспирантура по математике, 89 , Атлантическая ассоциация исследований в области математических наук (AARMS), Галифакс, штат Нью-Йорк, стр. 7, DOI : 10,1090 / GSM / 089 , ISBN 978-0-8218-4467-0, Руководство по ремонту 2389013.
- ^ Wolk, Е. С. (1962), "Сопоставимость график дерева", Труды Американского математического общества , 13 : 789-795, DOI : 10,2307 / 2034179 , МР 0172273.
- ^ Хватал, Вацлав ; Hammer, Peter Ladislaw (1977), «Агрегация неравенств в целочисленном программировании», в Hammer, PL; Джонсон, ЭЛ; Korte, BH; Немхаузер, GL (ред.), Исследования в области целочисленного программирования (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, 1 , Amsterdam: North-Holland, pp. 145–162.
- ^ Бонато, Энтони; Кемкес, Грэм; Prałat, Paweł (2012), "Почти все отговорка выиграть графики содержат универсальную вершину", Дискретная математика , 312 (10): 1652-1657, DOI : 10.1016 / j.disc.2012.02.018 , MR 2901161.
Внешние ссылки
- Вайсштейн, Эрик В. , «Конический граф» , MathWorld