Sokoldalú felső

Az univerzális csúcs egy irányítatlan gráf olyan csúcsa , amely szomszédos a gráf összes többi csúcsával. Nevezhetjük domináns csomópontnak is, mert egy egyszemélyes domináns halmazt alkot a gráfban.

Az univerzális csúcsot tartalmazó gráfot kúpnak is nevezhetjük . Ebben az összefüggésben egy univerzális csúcs nevezhető a kúp csúcsának [1] , de ez ütközik a csúcsgráfok terminológiájával , amelyben a csúcsot néha olyan csúcsnak nevezik, amelynek eltávolítása a gráfot síkré teszi.

Speciális gráfcsaládokban

A csillagok pontosan olyan fák , amelyeknek univerzális csúcsuk van, és úgy építhetők fel, hogy egy univerzális csúcsot adunk egy független halmazhoz . Hasonlóképpen kerekek is előállíthatók úgy, hogy egy univerzális csúcsot adunk a ciklushoz [2] . A geometriában a háromdimenziós piramisok vázai kerekek , és bármely dimenziójú térben lévő bármely piramis általánosabb grafikonjainak univerzális csúcsa a piramis csúcsa (csúcs).

A triviálisan tökéletes gráfok ( fák összehasonlíthatósági gráfjai a halmazelméletből ) mindig tartalmaznak egy univerzális csúcsot, nevezetesen a fa gyökerét, és olyan gráfokként írhatók le, amelyekben bármely generált részgráf tartalmaz egy univerzális csúcsot [3] . A tökéletes küszöbgráfok triviálisan tökéletes gráfok alosztályát alkotják, tehát egy univerzális csúcsot tartalmaznak. Meghatározhatók gráfokként, amelyek egy univerzális csúcs vagy egy izolált csúcs (vagyis élek nélküli csúcs) ismételt hozzáadásával állíthatók elő [4] .

Minden univerzális csúcsú gráf elemezhető , és szinte minden elemezhető gráfnak van univerzális csúcsa [5] .

Egyéb tulajdonságok

Egy n csúcsú gráfban univerzális csúcsnak nevezzük azt a csúcsot, amelynek foka pontosan n − 1 . Ezért az osztott gráfokhoz hasonlóan az univerzális csúcsgráfok is felismerhetők pusztán a fokozati sorrendjük alapján , anélkül, hogy megnéznénk a gráfok szerkezetét.

Jegyzetek

  1. Larrión, de Mello, Morgana, Neumann-Lara, Pizaña, 2004 , p. 183–191.
  2. Bonato, 2008 , p. 7.
  3. Wolk, 1962 , p. 789–795.
  4. Chvatal, Hammer, 1977 , p. 145–162.
  5. Bonato, Kemkes, Prałat, 2012 , p. 1652–1657

Irodalom

Linkek