完全点
在图论中，完全点（universal vertex）是一个在无向图中与其余所有顶点有连接的顶点。其又称作支配点（dominating vertex），因为它在图中形成了一个单元素支配集。
仅有一个完全点的图又称为椎体。在这种情况下，完全点称为椎体的顶点。[1]然而，这个术语与顶点图中的术语相冲突，在顶点图中顶点若被删除，留下的子图为平面图。
特殊图类
[编辑]星图正是树图中含有一个完全点的图，且星图可以由向独立集中添加一个完全点来构造。类似地，轮图可以由向环形图中添加一个完全点来构造。[2]在几何学中，三维金字塔以轮图为骨架，其可推广为任何更高维金字塔的图都有一个完全点作为金字塔的顶点。
完备图(集合论中树的可比性图)总是包含一个完全点，即树的根，更准确地说其可以被描述为每个连通的导出子图都包含一个完全点的图。[3]连通阈值图是完备图的一个子类，因此它也包含一个完全点。其可以被定义为通过重复添加完全点或一个孤立点(没有关联边的顶点)而形成的图。[4]
每个含有完全点的图都是一个可拆解图，并且几乎所有可拆解图都有一个完全点。[5]
其他属性
[编辑]在一个有n个顶点的图中，一个完全点的度恰好为n - 1。因此，像分裂图一样，具有一个完全点的图不需要查看图结构，可以只通过它们的度序列区分开。
参考文献
[编辑]- ^ 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): 183–191, MR 2059518, doi:10.1016/j.disc.2003.10.023
- ^ Bonato, Anthony, A course on the web graph, Graduate Studies in Mathematics 89, Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS: 7, 2008 [2019-05-22], ISBN 978-0-8218-4467-0, MR 2389013, doi:10.1090/gsm/089, （原始内容存档于2019-04-04）.
- ^ Wolk, E. S., The comparability graph of a tree, Proceedings of the American Mathematical Society, 1962, 13: 789–795, MR 0172273, doi:10.2307/2034179.
- ^ Chvátal, Václav; Hammer, Peter Ladislaw, Aggregation of inequalities in integer programming, Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (编), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics 1, Amsterdam: North-Holland: 145–162, 1977.
- ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł, Almost all cop-win graphs contain a universal vertex, Discrete Mathematics, 2012, 312 (10): 1652–1657, MR 2901161, doi:10.1016/j.disc.2012.02.018.