En strikt ackordsgraf

En oriktad graf G kallas strikt ackordal om den är ackordal och varje cykel med jämn längd ( ) i G har ett udda ackord , det vill säga en kant som förbinder två hörn av cykeln på ett udda avstånd (>1) från varandra [1] .

Beskrivning

Strängt ackordsgrafer beskrivs av förbjudna grafer som grafer som inte innehåller en genererad cykel på mer än tre längder eller en n -sun ( ) som en genererad subgraf [2] [3] [4] . n -Sun är en kordalgraf med 2n hörn uppdelade i två delmängder och så att varje vertex w i från W har exakt två grannar, u i och . n -Sun kan inte strikt vara ackord, eftersom cykeln ... inte har några udda ackord.

Strikt ackordsgrafer kan beskrivas som grafer som har en strikt perfekt elimineringsordning, en vertexordning så att grannarna till varje vertex som kommer senare i ordning bildar en klick , och sådana att för någon , om den i -te vertexen i ordningen är angränsande till k -th och l -th vertex , och j - th och k -th vertex är intilliggande, då måste både j -th och l -th vertexen ligga intill [3] [5] .

En graf är strikt ackordal om och endast om någon av dess genererade subgrafer har en enkel vertex, det vill säga en vertex vars grannar är linjärt ordnade efter inkluderingsordning [3] [6] . En graf är också strikt ackordal om och endast om den är ackordal och någon cykel med längd fem eller mer har en 2-ackordstriangel, det vill säga en triangel som bildas av två ackord och en kant av cykeln [7] .

En graf är strikt ackordal om och endast om någon av dess genererade subgrafer är en dual chordal graph [8] .

Strängt ackordsgrafer kan beskrivas i termer av antalet kompletta subgrafer som en kant hör till [9] . En annan beskrivning ges i tidningen av De Caria och McKee [10] .

Erkännande

Det är möjligt att avgöra om en graf är strikt ackordal i polynomtid genom att upprepade gånger söka efter och ta bort en enkel vertex. Om denna process eliminerar alla hörn i grafen, måste grafen vara strikt ackordal. Annars hittar processen inte en subgraf utan en enkel vertex, och i det här fallet kan den ursprungliga grafen inte vara strikt ackordal. För en strikt ackordal graf kallas ordningen i vilken hörn tas bort i denna process den strikta perfekta elimineringsordningen [3] .

Alternativa algoritmer är kända som kan avgöra om en graf är strikt ackordal och i så fall konstruera en strikt perfekt elimineringsordning mer effektivt, i tid, för en graf med n hörn och m kanter [11] [12] [13] .

Underklasser

En viktig underklass (baserat på fylogeni ) är klassen k - bladsgrader , det vill säga grafer som bildas av löv på ett träd genom att två löv kopplas samman med en kant om avståndet i trädet inte överstiger k . En bladgrad är en graf som är en k -bladsgrad för vissa k . Eftersom graderna av strikt kordagrafer är strikt korda och träd är strikt kordala, följer det att bladgrader är strikt kordala. De bildar sin egen underklass av starkt ackordsgrafer, som i sin tur inkluderar klustergrafer som 2-arks potenser [14] . En annan viktig underklass av strikt ackordsgrafer är intervallgrafer . Branstedt, Hudt, Mancini och Wagner [15] visade att intervallgrafer och en större klass av riktade rotbanor är bladkrafter.

Algoritmiska problem

Eftersom starkt ackordala grafer är både ackordala och dubbelackordala , kan olika NP-kompletta problem som det oberoende uppsättningsproblemet , klickproblemet , färgläggningen , klicktäckningsproblemet , dominerande uppsättningen och Steiner-minimalträdsproblemet lösas effektivt för starkt ackordala grafer. Grafisomorfismproblemet är GI-komplett [16] för strikt ackordsgrafer [17] . Sökandet efter Hamilton-cykler förblir ett NP-komplett problem för strikt ackordsdelade grafer [18] .

Anteckningar

  1. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 43, Definition 3.4.1.
  2. ↑ Chang, 1982 .
  3. ↑ 1 2 3 4 Farber, 1983 .
  4. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 112, sats 7.2.1.
  5. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 77, sats 5.5.1.
  6. ↑ Brandstädt, Le, Spinrad, 1999 , sid. 78, sats 5.5.2.
  7. ↑ Dahlhaus, Manuel, Miller, 1998 .
  8. ↑ Brandstädt, Dragan, Chepoi, Voloshin, 1998 , sid. 444, följd 3.
  9. ↑ McKee, 1999 .
  10. ↑ De Caria, McKee, 2014 .
  11. ↑ Lubiw, 1987 .
  12. ↑ Paige, Tarjan, 1987 .
  13. ↑ Spinrad, 1993 .
  14. ↑ Nishimura, Ragde, Thilikos, 2002 .
  15. ↑ Brandstädt, Hundt, Mancini, Wagner, 2010 .
  16. ↑ Artikeln introducerar en ny fullständighetsklass - Graph Isomorphism completeness
  17. ↑ Uehara, Toda, Nagoya, 2005 .
  18. ↑ Müller, 1996 .

Litteratur