Triviálisan tökéletes grafikon

A triviálisan tökéletes gráf  egy olyan gráf, amelynek az a tulajdonsága, hogy minden egyes generált részgráfjában a maximális (méretben) független halmaz mérete megegyezik a maximális klikkek számával [1] [2] . A triviálisan tökéletes gráfokat először Volk [3] [4] tanulmányozta , de a nevet Golumbik [2] adta . Golumbik azt írta, hogy "ezt a nevet azért választották, mert az ilyen gráfok tökéletességének bizonyítása triviális volt ." A triviálisan tökéletes gráfok fa összehasonlíthatósági gráfok [3] [4] , fa összehasonlíthatósági gráfok [5] és kváziküszöb gráfok [6] néven is ismertek .

Egyenértékű leírások

A triviálisan tökéletes gráfoknak számos más ekvivalens leírása van:

• Ezek a fák összehasonlíthatósági grafikonjai a rendelméletből . Vagyis legyen T  olyan parciális rend , hogy bármely t ∈ T esetén az { s ∈ T  : s < t } halmaz jól rendezett < relációval, és T -nek van a legkisebb r eleme . Ekkor a T rendű összehasonlíthatósági gráf triviálisan tökéletes, és így bármilyen triviálisan tökéletes gráf előállítható [7] [8] .
• Ezek olyan gráfok, amelyek generált részgráfokként nem tartalmaznak P 4 útvonalat vagy C 4 ciklust [7] [9] [10]
• Ezek olyan gráfok, amelyekben minden összekapcsolt generált részgráf tartalmaz egy univerzális csúcsot [11] .
• Ezek olyan gráfok, amelyek beágyazott tartományok intervallumgráfjainak tekinthetők . A rések halmaza akkor rendelkezik a beágyazó tulajdonsággal, ha a halmaz bármely két résénél vagy nem metszik egymást, vagy az egyiket a másik tartalmazza [12] .
• Olyan gráfokról van szó, amelyek egyszerre akkordgráfok és kográfok [13] [14] . Ez következik az akkordgráfok leírásából, mint a négy vagy annál hosszabb generált ciklus nélküli gráfok és a kográfok, mint a négy csúcsú generált útvonalak nélküli gráfok ( P4 ) .
• Olyan gráfokról van szó, amelyek egyszerre kográfok és intervallumgráfok [13] [14] .
• Ezek olyan gráfok, amelyek egy csúcsú gráfokból kiindulva alakíthatók ki két művelettel - két kisebb triviálisan tökéletes gráf diszjunkt uniójával és egy új csúcs hozzáadásával a kisebb triviálisan tökéletes gráf összes csúcsához [6] [15] . Ezek a műveletek egy új erdő kialakításának felelnek meg két kisebb erdő szétválasztásával, és egy fa kialakításának, ha egy új gyökeret kapcsolnak az erdőben lévő összes fa gyökeréhez.
• Ezek olyan gráfok, amelyekben bármely uv él esetén az u és v csúcsok környezetei (beleértve magukat az u -t és v -t is ) egymásba vannak ágyazva – az egyik szomszédságnak a másik szomszédságában kell lennie [14] .
• Ezek a [16] veremben rendezett permutációkból definiált permutációs gráfok .
• Ezek olyan grafikonok, amelyeknek az a tulajdonsága, hogy minden egyes generált részgráfjában a klikk lefedettség száma megegyezik a maximális klikkek számával [17] .
• Ezek olyan gráfok, amelyeknek az a tulajdonsága, hogy mindegyik generált részgráfjában a klikkszám megegyezik a Grandi pszeudoszámmal [17] .
• Ezek olyan gráfok, amelyeknek az a tulajdonsága, hogy az egyes generált részgráfok kromatikus száma megegyezik a pszeudo Grandi-számmal [17] .

Kapcsolódó gráfosztályok

A triviálisan tökéletes gráfok ekvivalens leírásából az következik, hogy minden triviálisan tökéletes gráf egyben kográf , akkord- , ptolemaioszi , intervallum- és tökéletes gráf is .

A küszöbgráfok  pontosan azok a gráfok, amelyek triviálisan tökéletesek és triviálisan tökéletes gráfok (triviálisan tökéletes kográfok) komplementerei [18] [19] .

A malmok triviálisan tökéletesek.

Elismerés

Chu [20] egy egyszerű lineáris idő algoritmust ír le triviálisan tökéletes gráfok felismerésére a lexikográfiai szélességi keresés alapján . Amikor a LexBFS algoritmus eltávolítja v -t a várólista első halmazából, az algoritmus ellenőrzi, hogy v összes többi szomszédja ugyanabban a halmazban van-e. Ha nem, akkor a tiltott generált részgráfok egyike felépíthető v -ből . Ha az ellenőrzés minden v esetén sikeres , akkor a gráf triviálisan tökéletes. Az algoritmus módosítható úgy, hogy lineáris időben tesztelje, hogy egy gráf egy triviálisan tökéletes gráf komplementere -e.

Annak meghatározása, hogy egy általános gráfból k él eltávolítása után triviálisan tökéletes gráf lesz-e, NP-teljes feladat [21] , fix paraméterrel megoldható [22] , és O(2,45 k (m+n) ) ) idő alatt megoldható [ 23] .

Jegyzetek

1. ↑ Brandstädt, Le, Spinrad, 1999 , p. 34 definíció 2.6.2.
2. ↑ 1 2 Golumbic, 1978 .
3. ↑ 12 Wolk , 1962 .
4. ↑ 12 Wolk , 1965 .
5. ↑ Donnelly, Isaak, 1999 .
6. ↑ 12 Yan , Chen, Chang, 1996 .
7. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 99 6.6.1. tétel.
8. ↑ Golumbic, 1978 , p. következmény 4.
9. ↑ Golumbic, 1978 , p. 2. tétel.
10. ↑ Wolk 1962 bebizonyította ezt a gyökeres erdők összehasonlíthatósági grafikonjainál.
11. ↑ Wolk (1962) .
12. ↑ Brandstädt, Le, Spinrad, 1999 , p. 51.
13. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 248.
14. ↑ 1 2 3 Yan, Chen, Chang, 1996 , p. 3. tétel.
15. ↑ Gurski, 2006 .
16. ↑ Rotem, 1981 .
17. ↑ 1 2 3 Rubio-Montiel (2015) .
18. ↑ Brandstädt, Le, Spinrad, 1999 , p. 100 Tétel 6.6.3.
19. ↑ Golumbic, 1978 , p. következmény 5.
20. ↑ Chu, 2008 .
21. ↑ Sharan (2002) .
22. ↑ Cai (1996) .
23. ↑ Nastos, Gao, 2010 .

Irodalom

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Grafikonosztályok: Felmérés. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 0-89871-432-X .
• Cai L. Örökletes tulajdonságok gráfmódosítási problémáinak fixparaméteres kezelhetősége // Information Processing Letters . - 1996. - T. 58 , sz. 4 . – S. 171–176 . - doi : 10.1016/0020-0190(96)00050-6 .
• Frank Pok Man Chu. Egy egyszerű lineáris időhitelesítő LBFS-alapú algoritmus triviálisan tökéletes gráfok és komplementereik felismerésére // Information Processing Letters . - 2008. - T. 107 , sz. 1 . – 7–12.o . - doi : 10.1016/j.ipl.2007.12.009 .
• Sam Donnelly, Garth Isaak. Hamiltoni hatványok küszöb- és arboreszcens összehasonlíthatósági gráfokban // Diszkrét matematika . - 1999. - T. 202 , sz. 1-3 . – 33–44 . - doi : 10.1016/S0012-365X(98)00346-X .
• Martin Charles Golumbic. Triviálisan tökéletes gráfok // Diszkrét matematika . - 1978. - T. 24 , sz. 1 . – S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
• Frank Gurski. A korlátozott NLC-szélességű vagy klikkszélesség-műveletek által meghatározott kográfok jellemzései // Discrete Mathematics . - 2006. - T. 306 , sz. 2 . – S. 271–277 . - doi : 10.1016/j.disc.2005.11.014 .
• James Nastos, Yong Gao. Új elágazási stratégia paraméterezett gráfmódosítási problémákra // Számítástechnikai előadásjegyzetek. - 2010. - T. 6509 . – S. 332–346 .
• Rotem D. Rendezhető permutációk halmozása // Discrete Mathematics . - 1981. - T. 33 , sz. 2 . – S. 185–196 . - doi : 10.1016/0012-365X(81)90165-5 .
• Rubio-Montiel C. A triviálisan tökéletes gráfok új jellemzése // Electronic Journal of Graph Theory and Applications. - 2015. - 3. évf . 1 . – S. 22–26 . - doi : 10.5614/ejgta.2015.3.1.3 .
• Roded Sharan. Gráfmódosítási problémák és alkalmazásaik a genomikai kutatásban // PhD értekezés, Tel Aviv University. – 2002.
• Wolk ES Egy fa összehasonlíthatósági grafikonja // Proceedings of the American Mathematical Society . - 1962. - T. 13 , sz. 5 . – S. 789–795 . - doi : 10.1090/S0002-9939-1962-0172273-0 .
• Wolk ES Megjegyzés a fa összehasonlíthatósági grafikonjához // Proceedings of the American Mathematical Society . - 1965. - T. 16 . — S. 17–20 . - doi : 10.1090/S0002-9939-1965-0172274-5 .
• Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Kvázi-küszöb gráfok // Discrete Applied Mathematics . - 1996. - T. 69 , sz. 3 . – S. 247–255 . - doi : 10.1016/0166-218X(96)00094-7 .

Linkek

• Triviálisan tökéletes grafikonok , Információs rendszer a gráfosztályokról és azok zárványairól , < http://www.graphclasses.org/classes/gc_327.html >