| 词条 | Universal vertex |
| 释义 |
Not to be confused with a universally quantified vertex in the logic of graphs. In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. A graph that contains a universal vertex may be called a cone. In this context, the universal vertex may also be called the apex of the cone.[1] However, this terminology conflicts with the terminology of apex graphs, in which an apex is a vertex whose removal leaves a planar subgraph. In special families of graphsThe stars are exactly the trees that have a universal vertex, and may be constructed by adding a universal vertex to an independent set. The wheel graphs, similarly, may be formed by adding a universal vertex to a cycle graph.[2] In geometry, the three-dimensional pyramids have wheel graphs as their skeletons, and more generally the graph of any higher-dimensional pyramid has a universal vertex as the apex of the pyramid. The trivially perfect graphs (the comparability graphs of order-theoretic trees) always contain a universal vertex, the root of the tree, and more strongly they may be characterized as the graphs in which every connected induced subgraph contains a universal vertex.[3] The connected threshold graphs form a subclass of the trivially perfect graphs, so they also contain a universal vertex; they may be defined as the graphs that can be formed by repeated addition of either a universal vertex or an isolated vertex (one with no incident edges).[4] Every graph with a universal vertex is a dismantlable graph, and almost all dismantlable graphs have a universal vertex.[5] Other propertiesIn a graph with {{mvar|n}} vertices, a universal vertex is a vertex whose degree is exactly {{math|n − 1}}. Therefore, like the split graphs, graphs with a universal vertex can be recognized purely by their degree sequences, without looking at the structure of the graph. References1. ^{{citation | last1 = Larrión | first1 = F. | last2 = de Mello | first2 = C. P. | last3 = Morgana | first3 = A. | last4 = Neumann-Lara | first4 = V. | last5 = Pizaña | first5 = M. A. | doi = 10.1016/j.disc.2003.10.023 | issue = 1-3 | journal = Discrete Mathematics | mr = 2059518 | pages = 183–191 | title = The clique operator on cographs and serial graphs | volume = 282 | year = 2004}}. 2. ^{{citation | last = Bonato | first = Anthony | doi = 10.1090/gsm/089 | isbn = 978-0-8218-4467-0 | mr = 2389013 | page = 7 | publisher = Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS | series = Graduate Studies in Mathematics | title = A course on the web graph | url = https://books.google.com/books?id=gv4OCgAAQBAJ&pg=PA7 | volume = 89 | year = 2008}}. 3. ^{{citation | last = Wolk | first = E. S. | journal = Proceedings of the American Mathematical Society | mr = 0172273 | pages = 789–795 | title = The comparability graph of a tree | volume = 13 | year = 1962 | doi = 10.2307/2034179}}. 4. ^{{citation | last1 = Chvátal | first1 = Václav | author1-link = Václav Chvátal | last2 = Hammer | first2 = Peter Ladislaw | author2-link = Peter Ladislaw Hammer | contribution = Aggregation of inequalities in integer programming | editor1-last = Hammer | editor1-first = P. L. | editor2-last = Johnson | editor2-first = E. L. | editor3-last = Korte | editor3-first = B. H. | editor4-last = Nemhauser | editor4-first = G. L. | location = Amsterdam | pages = 145–162 | publisher = North-Holland | series = Annals of Discrete Mathematics | title = Studies in Integer Programming (Proc. Worksh. Bonn 1975) | volume = 1 | year = 1977}}. 5. ^{{citation | last1 = Bonato | first1 = Anthony | last2 = Kemkes | first2 = Graeme | last3 = Prałat | first3 = Paweł | doi = 10.1016/j.disc.2012.02.018 | issue = 10 | journal = Discrete Mathematics | mr = 2901161 | pages = 1652–1657 | title = Almost all cop-win graphs contain a universal vertex | volume = 312 | year = 2012}}. External links
1 : Graph theory objects |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。