Univerzális csúcs

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf univerzális csúcsa a gráf összes többi csúcsával szomszédos. Nevezik domináló csúcsnak is, mivel a gráf egy elemből álló domináló halmazát alkotja. Egy $n$ csúcsú gráfban a domináló csúcs fokszáma éppen $n - 1$ . Ezért, a split gráfokhoz hasonlóan, az univerzális csúccsal rendelkező gráfok fokszámsorozatuk alapján, a gráf szerkezetének külön vizsgálata nélkül is felismerhetők.

Az univerzális csúcsot tartalmazó gráfot kúpnak (cone) is nevezik. Ebben a kontextusban az univerzális csúcs a gráf csúcspontja (apex).^[1] Ez a terminológia azonban ütközik a csúcsgráfokéval, ahol a csúcspont olyan csúcsot jelent, melynek eltávolítása után síkbarajzolható gráf marad hátra.

A csillaggráfok pontosan azok a fák, melyek rendelkeznek univerzális csúccsal; megalkothatók a független csúcshalmazhoz egy univerzális csúcs hozzáadásával. A kerékgráfok hasonlóak képezhetők egy körgráfhoz univerzális csúcsot hozzáadva.^[2] A geometriában a háromdimenziós gúlák vázát kerékgráfok adják, általánosabban pedig bármely magasabb dimenziós gúla „legmagasabb csúcsa” megegyezik a gúlához tartozó gráf univerzális csúcsával.

A triviálisan perfekt gráfok (a halmazelméleti értelemben vett fák összehasonlíthatósági gráfjai) mindig tartalmaznak univerzális csúcsot, ami a fa gyökere; úgy is jellemezhetők, mint azok a gráfok, melyek minden összefüggő feszített részgráfja tartalmaz univerzális csúcsot.^[3] Az összefüggő küszöbgráfok a triviálisan perfekt gráfok alosztályát képezik, így szintén tartalmaznak univerzális csúcsot; ezek a gráfok úgy is definiálhatók, mint a gráfok, melyek előállíthatók izolált csúcsok és univerzális csúcsok felváltva történő hozzáadásával.^[4]

Minden, univerzális csúccsal rendelkező gráf szétszerelhető (wd), és csaknem minden szétszerelhető gráfban van univerzális csúcs.^[5]

Fordítás

Ez a szócikk részben vagy egészben az Universal vertex című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Larrión, F.; de Mello, C. P. & Morgana, A. et al. (2004), "The clique operator on cographs and serial graphs", Discrete Mathematics 282 (1-3): 183–191, DOI 10.1016/j.disc.2003.10.023.
↑ Bonato, Anthony (2008), A course on the web graph, vol. 89, Graduate Studies in Mathematics, Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, p. 7, ISBN 978-0-8218-4467-0, doi:10.1090/gsm/089, <https://books.google.com/books?id=gv4OCgAAQBAJ&pg=PA7>.
↑ Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society 13: 789–795, DOI 10.2307/2034179.
↑ Chvátal, Václav & Hammer, Peter Ladislaw (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L. & Korte, B. H. et al., Studies in Integer Programming (Proc. Worksh. Bonn 1975), vol. 1, Annals of Discrete Mathematics, Amsterdam: North-Holland, pp. 145–162.
↑ Bonato, Anthony; Kemkes, Graeme & Prałat, Paweł (2012), "Almost all cop-win graphs contain a universal vertex", Discrete Mathematics 312 (10): 1652–1657, DOI 10.1016/j.disc.2012.02.018.

További információk

Weisstein, Eric W.: Cone Graph (angol nyelven). Wolfram MathWorld

[1] Larrión, F.; de Mello, C. P. & Morgana, A. et al. (2004), "The clique operator on cographs and serial graphs", Discrete Mathematics 282 (1-3): 183–191, DOI 10.1016/j.disc.2003.10.023.

[2] Bonato, Anthony (2008), A course on the web graph, vol. 89, Graduate Studies in Mathematics, Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, p. 7, ISBN 978-0-8218-4467-0, doi:10.1090/gsm/089, <https://books.google.com/books?id=gv4OCgAAQBAJ&pg=PA7>.

[3] Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society 13: 789–795, DOI 10.2307/2034179.

[4] Chvátal, Václav & Hammer, Peter Ladislaw (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L. & Korte, B. H. et al., Studies in Integer Programming (Proc. Worksh. Bonn 1975), vol. 1, Annals of Discrete Mathematics, Amsterdam: North-Holland, pp. 145–162.

[5] Bonato, Anthony; Kemkes, Graeme & Prałat, Paweł (2012), "Almost all cop-win graphs contain a universal vertex", Discrete Mathematics 312 (10): 1652–1657, DOI 10.1016/j.disc.2012.02.018.

[1]

[2]

[3]

[4]

[5]