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ő , és csaknem minden szétszerelhető gráfban van univerzális csúcs.[5]
Fordítás szerkeszté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 szerkesztés
- ↑ 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 szerkesztés
- Weisstein, Eric W.: Cone Graph (angol nyelven). Wolfram MathWorld