完全點
在圖論中，完全點（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.