Trivialt perfekt graf

En trivialt perfekt graf  är en graf med egenskapen att i var och en av dess genererade subgrafer är storleken på den maximala (i storlek) oberoende uppsättningen lika med antalet maximala klick [1] [2] . Trivialt perfekta grafer studerades först av Volk [3] [4] , men namnet gavs av Golumbik [2] . Golumbik skrev att "det här namnet valdes med tanke på trivialiteten i att bevisa att sådana grafer är perfekta ." Trivialt perfekta grafer är också kända som trädjämförbarhetsgrafer [3] [4] , trädjämförbarhetsgrafer [5] och kvasithreshold-grafer [6] .

Motsvarande beskrivningar

Trivialt perfekta grafer har flera andra motsvarande beskrivningar:

• De är jämförbarhetsgrafer av träd från ordningsteori . Det vill säga låt T  vara en partiell ordning så att för varje t ∈ T mängden { s ∈ T  : s < t } är välordnad med relation < och T har det minsta elementet r . Då är jämförbarhetsgrafen av ordning T trivialt perfekt och vilken trivialt perfekt graf som helst kan bildas på detta sätt [7] [8] .
• De är grafer som inte innehåller en P 4 - väg eller en C 4 -cykel som genererade subgrafer [7] [9] [10]
• De är grafer där varje ansluten genererad subgraf innehåller en universell vertex [11] .
• De är grafer som kan ses som intervallgrafer för en uppsättning kapslade spann . En uppsättning luckor har kapslingsegenskapen om de för två mellanrum från uppsättningen antingen inte skär varandra, eller om en av dem finns i den andra [12] .
• De är grafer som är både ackordsgrafer och kografer [13] [14] . Detta följer av beskrivningen av ackordsgrafer som grafer utan genererade cykler med längd fyra eller fler och kografer som grafer utan genererade banor med fyra hörn ( P 4 ).
• De är grafer som är både kografer och intervallgrafer [13] [14] .
• De är grafer som kan bildas med utgångspunkt från grafer med en vertex, med två operationer - en disjunkt förening av två mindre trivialt perfekta grafer och lägga till en ny vertex intill alla hörn av den mindre trivialt perfekta grafen [6] [15] . Dessa operationer motsvarar bildandet av en ny skog genom att osammanfoga två mindre skogar, och bildandet av ett träd genom att foga en ny rot till rötterna på alla träden i skogen.
• De är grafer där, för varje kant uv , grannskapen av hörnen u och v (inklusive u och v själva ) är kapslade - en grannskap måste vara en grannskap till den andra [14] .
• De är permutationsgrafer definierade från permutationer sorterade på stacken [16] .
• De är grafer med egenskapen att i var och en av dess genererade subgrafer är antalet klicktäckningar lika med antalet maximala klick [17] .
• De är grafer med egenskapen att i var och en av dess genererade subgrafer är klicknumret lika med Grandi-pseudo- numret [17] .
• De är grafer med egenskapen att det kromatiska numret för var och en av dess genererade subgrafer är lika med pseudo Grandi-talet [17] .

Relaterade grafklasser

Det följer av motsvarande beskrivningar av trivialt perfekta grafer att alla trivialt perfekta grafer också är en kograf , ackord , ptolemaisk , intervall och perfekt graf .

Tröskelgrafer  är exakt de grafer som både är trivialt perfekta och är komplementet till trivialt perfekta grafer (trivialt perfekta kografer) [18] [19] .

Mills är trivialt perfekta.

Erkännande

Chu [20] beskriver en enkel linjär tidsalgoritm för att känna igen trivialt perfekta grafer baserat på lexikografisk bredd-först-sökning . När LexBFS-algoritmen tar bort v från den första uppsättningen i kön, kontrollerar algoritmen att alla återstående grannar till v är i samma uppsättning. Om inte kan en av de förbjudna genererade subgraferna byggas från v . Om kontrollen lyckas för alla v , är grafen trivialt perfekt. Algoritmen kan modifieras för att testa i linjär tid om en graf är komplementet till en trivialt perfekt graf.

Att avgöra om en allmän graf efter att ha tagit bort k kanter blir en trivialt perfekt graf är ett NP-komplett problem [21] , lösbart med fasta parametrar [22] , och det kan lösas i tiden O(2,45 k (m+n) ) [ 23] .

Anteckningar

1. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 34 definition 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 , sid. 99 Sats 6.6.1.
8. ↑ Golumbic, 1978 , sid. följd 4.
9. ↑ Golumbic, 1978 , sid. sats 2.
10. ↑ Wolk 1962 bevisade detta för rotade skogsjämförbarhetsgrafer.
11. ↑ Wolk (1962) .
12. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 51.
13. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , sid. 248.
14. ↑ 1 2 3 Yan, Chen, Chang, 1996 , sid. sats 3.
15. ↑ Gurski, 2006 .
16. ↑ Rotem, 1981 .
17. ↑ 1 2 3 Rubio-Montiel (2015) .
18. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 100 Sats 6.6.3.
19. ↑ Golumbic, 1978 , sid. följd 5.
20. ↑ Chu, 2008 .
21. ↑ Sharan (2002) .
22. ↑ Cai (1996) .
23. ↑ Nastos, Gao, 2010 .

Litteratur

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Grafklasser: En undersökning. - SIAM Monographs on Discrete Mathematics and Applications, 1999. - ISBN 0-89871-432-X .
• Cai L. Hanterbarhet med fasta parametrar för grafmodifieringsproblem för ärftliga egenskaper // Information Processing Letters . - 1996. - T. 58 , nr. 4 . — S. 171–176 . - doi : 10.1016/0020-0190(96)00050-6 .
• Frank Pok Man Chu. En enkel linjär tidscertifierande LBFS-baserad algoritm för att känna igen trivialt perfekta grafer och deras komplement // Information Processing Letters . - 2008. - T. 107 , nr. 1 . — s. 7–12 . - doi : 10.1016/j.ipl.2007.12.009 .
• Sam Donnelly, Garth Isaak. Hamiltonianska makter i tröskel- och arborescerande jämförbarhetsgrafer // Diskret matematik . - 1999. - T. 202 , nr. 1-3 . — s. 33–44 . - doi : 10.1016/S0012-365X(98)00346-X .
• Martin Charles Golumbic. Trivialt perfekta grafer // Diskret matematik . - 1978. - T. 24 , nr. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
• Frank Gurski. Karakteriseringar för ko-grafer definierade av begränsad NLC-bredd eller klickbreddsoperationer // Diskret matematik . - 2006. - T. 306 , nr. 2 . — S. 271–277 . - doi : 10.1016/j.disc.2005.11.014 .
• James Nastos, Yong Gao. A Novel Branching Strategy for Parameterized Graph Modification Problems // Föreläsningsanteckningar i datavetenskap. - 2010. - T. 6509 . — S. 332–346 .
• Rotem D. Stack sorterbara permutationer // Diskret matematik . - 1981. - T. 33 , nr. 2 . — S. 185–196 . - doi : 10.1016/0012-365X(81)90165-5 .
• Rubio-Montiel C. En ny karaktärisering av trivialt perfekta grafer // Electronic Journal of Graph Theory and Applications. - 2015. - Vol. 3 , nr. 1 . — S. 22–26 . - doi : 10.5614/ejgta.2015.3.1.3 .
• Roded Sharan. Grafmodifieringsproblem och deras tillämpningar på genomforskning // PhD Thesis, Tel Aviv University. – 2002.
• Wolk ES Jämförbarhetsgrafen för ett träd // Proceedings of the American Mathematical Society . - 1962. - T. 13 , nr. 5 . — S. 789–795 . - doi : 10.1090/S0002-9939-1962-0172273-0 .
• Wolk ES En anteckning om jämförbarhetsgrafen för ett träd // 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. Kvasitröskeldiagram // Diskret tillämpad matematik . - 1996. - T. 69 , nr. 3 . — S. 247–255 . - doi : 10.1016/0166-218X(96)00094-7 .

Länkar

• Trivialt perfekta grafer , informationssystem om grafklasser och deras inkludering , < http://www.graphclasses.org/classes/gc_327.html >