Univerzální vrchol - Universal vertex

v teorie grafů, a univerzální vrchol je vrchol z neorientovaný graf který sousedí se všemi ostatními vrcholy grafu. Může se také nazývat a dominující vrchol, protože tvoří jeden prvek dominující sada v grafu. (Nesmí být zaměňována s všeobecně kvantifikováno vrchol v logika grafů.)

Graf, který obsahuje univerzální vrchol, lze nazvat a kužel. V této souvislosti lze univerzální vrchol nazvat také vrchol kužele.[1] Tato terminologie je však v rozporu s terminologií vrcholové grafy, ve kterém vrchol je vrchol, jehož odstranění zanechává rovinný podgraf.

Ve speciálních rodinách grafů

The hvězdy jsou přesně stromy které mají univerzální vrchol a mohou být vytvořeny přidáním univerzálního vrcholu k nezávislá sada. The grafy kol, podobně, může být vytvořen přidáním univerzálního vrcholu k a graf cyklu.[2] V geometrii trojrozměrný pyramidy mít grafy kol jako jejich kostry a obecněji má graf jakékoli výškové pyramidy univerzální vrchol jako vrchol pyramidy.

The triviálně dokonalé grafy (dále jen srovnatelné grafy z řádově-teoretické stromy ) vždy obsahují univerzální vrchol, kořen stromu a silněji je lze charakterizovat jako grafy, ve kterých každý připojený indukovaný podgraf obsahuje univerzální vrchol.[3]Připojený prahové grafy tvoří podtřídu triviálně dokonalých grafů, takže obsahují také univerzální vrchol; mohou být definovány jako grafy, které mohou být vytvořeny opakovaným přidáním buď univerzálního vrcholu nebo izolovaného vrcholu (jednoho bez dopadajících hran).[4]

Každý graf s univerzálním vrcholem je a demontovatelný graf a téměř všechny demontovatelné grafy mají univerzální vrchol.[5]

Další vlastnosti

V grafu s n vrcholy, univerzální vrchol je vrchol, jehož stupeň je přesně n − 1. Proto, jako rozdělené grafy, grafy s univerzálním vrcholem lze rozpoznat čistě podle jejich stupně, aniž byste se dívali na strukturu grafu.

Reference

  1. ^ Larrión, F .; de Mello, C. P .; Morgana, A .; Neumann-Lara, V.; Pizaña, M. A. (2004), „Operátor kliky na grafech a sériových grafech“, Diskrétní matematika, 282 (1–3): 183–191, doi:10.1016 / j.disc.2003.10.023, PAN  2059518.
  2. ^ Bonato, Anthony (2008), Kurz webového grafu, Postgraduální studium matematiky, 89Atlantická asociace pro výzkum v matematických vědách (AARMS), Halifax, NS, s. 7, doi:10,1090 / gsm / 089, ISBN  978-0-8218-4467-0, PAN  2389013.
  3. ^ Wolk, E. S. (1962), „Graf srovnatelnosti stromu“, Proceedings of the American Mathematical Society, 13: 789–795, doi:10.2307/2034179, PAN  0172273.
  4. ^ Chvátal, Václav; Kladivo, Peter Ladislaw (1977), „Agregace nerovností v celočíselném programování“, Hammer, P. L .; Johnson, E. L .; Korte, B. H .; Nemhauser, G. L. (eds.), Studium programování celých čísel (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, 1, Amsterdam: Severní Holandsko, s. 145–162.
  5. ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), „Téměř všechny grafy typu cop-win obsahují univerzální vrchol“, Diskrétní matematika, 312 (10): 1652–1657, doi:10.1016 / j.disc.2012.02.018, PAN  2901161.

externí odkazy