Универсальная вершина
Универсальная вершина — это вершина неориентированного графа, которая смежна всем остальным вершинам графа. Она может также называться доминирующей вершиной, поскольку она образует одноэлементное доминирующее множество в графе.
Граф, который содержит универсальную вершину, может быть также назван конусом. В этом контексте универсальную вершину можно называть апексом конуса[1], однако это конфликтует с терминологией верхушечных графов, в которых иногда апексом называется вершина, удаление которой делает граф планарным.
В специальных семействах графов
[править | править код]Звёзды — это в точности деревья, которые имеют универсальную вершину и могут быть построены путём добавления универсальной вершины в независимое множество. Колёса, аналогично, могут быть образованы путём добавления универсальной вершины в цикл[2]. В геометрии трёхмерные пирамиды имеют колёса в качестве их остовов[англ.], а более общие графы любой пирамиды в пространстве любой размерности имеют универсальную вершину как вершину (апекс) пирамиды.
Тривиально совершенные графы (графы сравнимости деревьев из теории множеств) всегда содержат универсальную вершину, а именно, корень дерева, и могут быть описаны как графы, в которых любой порождённый подграф содержит универсальную вершину[3]. Совершенные пороговые графы образуют подкласс тривиально совершенных графов, так что они содержат универсальную вершину. Они могут быть определены как графы, которые могут быть образованы путём повторяющегося добавления либо универсальной вершины, либо изолированной вершины (то есть вершины без рёбер)[4].
Любой граф с универсальной вершиной разбираемый и почти все разбираемые графы имеют универсальную вершину[5].
Другие свойства
[править | править код]В графе с n вершинами универсальная вершина — это вершина, степень которой в точности равна n − 1. Поэтому, подобно расщепляемым графам, графы с универсальной вершиной могут быть распознаны чисто по их последовательности степеней без просмотра структуры графов.
Примечания
[править | править код]- ↑ Larrión, de Mello, Morgana, Neumann-Lara, Pizaña, 2004, с. 183–191.
- ↑ Bonato, 2008, с. 7.
- ↑ Wolk, 1962, с. 789–795.
- ↑ Chvátal, Hammer, 1977, с. 145–162.
- ↑ Bonato, Kemkes, Prałat, 2012, с. 1652–1657.
Литература
[править | править код]- Larrión F., de Mello C. P., Morgana A., Neumann-Lara V., Pizaña M. A. The clique operator on cographs and serial graphs // Discrete Mathematics. — 2004. — Т. 282, вып. 1-3. — P. 183–191. — doi:10.1016/j.disc.2003.10.023.
- Anthony Bonato. A course on the web graph. — Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, 2008. — Т. 89. — С. 7. — (Graduate Studies in Mathematics). — ISBN 978-0-8218-4467-0. — doi:10.1090/gsm/089.
- Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13. — С. 789–795. — doi:10.2307/2034179.
- Václav Chvátal, Peter Ladislaw Hammer. Aggregation of inequalities in integer programming // Studies in Integer Programming (Proc. Worksh. Bonn 1975) / Hammer P. L., Johnson E. L., Korte B. H., Nemhauser G. L.. — Amsterdam: North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics).
- Anthony Bonato, Graeme Kemkes, Paweł Prałat. Almost all cop-win graphs contain a universal vertex // Discrete Mathematics. — 2012. — Т. 312, вып. 10. — С. 1652–1657. — doi:10.1016/j.disc.2012.02.018.
Ссылки
[править | править код]- Weisstein, Eric W. Cone Graph (англ.) на сайте Wolfram MathWorld.
 | Для улучшения этой статьи желательно:
|