Kettős akkord gráf

Egy irányítatlan G gráf duálisan akkordális , ha maximális klikkhipergráfja egy hiperfa . Az elnevezés onnan ered, hogy egy gráf akkor és csak akkor akkordális , ha a maximális klikkhipergráfja duális egy hiperfához. Ezeket a gráfokat eredetileg a maximális szomszédság határozta meg, és számos különböző leírásuk van [1] [2] [3] . Az akkordgráfokkal ellentétben a duális akkord gráfok tulajdonsága nem öröklődik, vagyis a duális akkordgráf generált részgráfjai nem feltétlenül duálakkordok (az öröklődés értelmében a duális akkordgráfok pontosan a szigorúan akkord gráfok utódai), és A kettős akkord gráf általában nem tökéletes . A kettős akkord gráfok kezdetben HT-gráfok [4] [5] [6] néven jelentek meg .

Leírás

A duális akkordgráfok akkordgráfok klikkgráfjai [ 7 ] [8] , azaz akkordgráfok maximális klikkjeinek metszésgráfjai.

A következő tulajdonságok egyenértékűek az [1] [2] [9] [5] [6] tulajdonsággal :

• G maximális szomszédsági sorrenddel rendelkezik [ 10 ] . 
• A G gráfnak van egy T feszítőfája , hogy a G gráf bármely maximális klikkje létrehoz egy részfát T -ben .
• A G gráf zárt szomszédsági hipergráfja N(G) egy hiperfa [ .
• A G gráf maximális klikkjeinek hipergráfja egy hiperfa .
• G egy 2 szakaszból álló hiperfa gráf .

A zárt szomszédsági hipergráfra vonatkozó feltételből az is következik, hogy egy gráf akkor és csak akkor duálisan akkordális, ha a négyzete akkord, és a zárt szomszédsági hipergráfja rendelkezik a Helly tulajdonsággal .

De Caria és Gutirrez [11] cikke a duális akkordgráfokat ír le az elválasztók tulajdonságairól. Breshard cikkében [12] kimutatták, hogy a duális akkordgráfok pontosan az aciklikus köbös komplexek gráfjainak maximális hiperkockáinak metszésponti gráfjai.

A duplán akkordális gráfok szerkezetét és algoritmikus használatát Marina Moscarini adta meg [13] . Ezek akkord gráfok, amelyek egyszerre és duálisan akkordálisak.

Elismerés

A duális akkordgráfok lineáris időben felismerhetők, a duális akkordgráf maximális környezetének sorrendje pedig lineáris időben [2] [4] .

A problémák összetettsége

Míg az alapvető problémák, mint például a maximális független halmaz megtalálása , a maximális klikk , a színezés és a klikk lefedettség , NP-teljesek maradnak a kettős akkordgráfoknál, a Steiner-minimális domináns halmaz és a fa probléma egyes változatai hatékonyan megoldhatók kettős akkordgráfoknál (de a független a dominancia NP-teljes marad ) [2] [5] [6] . Lásd Branstadt, Chepoy és Dragan [14] a kettős akkord gráfok tulajdonságainak feszítőfa-problémákhoz való használatához, Branstadt, Leitert és Rautenbach [15] pedig a lineáris időcsúcs és éldominancia algoritmushoz.

Jegyzetek

1. ↑ 1 2 Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // Számítástechnikai előadásjegyzetek . - 1993. - T. 790 . – S. 237–251 .
2. ↑ 1 2 3 4 Andreas Brandstädt, Victor Chepoi, Feodor Dragan. A hiperfa-struktúra és a maximális szomszédsági sorrend algoritmikus használata // Discrete Applied Mathematics . - 1998. - T. 82 . – 43–77 . - doi : 10.1016/s0166-218x(97)00125-x .
3. ↑ 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 .
4. ↑ 1 2 Feodor Dragan. Grafikonok központjai és a Helly ingatlan (orosz nyelven). – Ph.D. szakdolgozat, Moldovai Állami Egyetem, Moldova, 1989.
5. ↑ 1 2 3 Feodor Dragan, Chiril Prisacaru, Victor Chepoi. Helymeghatározási problémák a gráfokban és a Helly tulajdonságban // Discrete Math. (Moszkva) . - 1992. - T. 4 . – 67–73 . ; F. F. Dragan, K. F. Prisakor, V. D. Chepoy. Helymeghatározási problémák grafikonokon és a Helly tulajdonságon  // Diskret. Mat.. - 1992. - V. 4 , sz. 4 . – 67–73 . ; Fedor Fedorovich Dragan. Középpontok a grafikonokban és a Helly tulajdonságban. - Minszk: BSSR Tudományos Akadémia. Matematikai Intézet, 1989. - (A fizikai és matematikai tudományok kandidátusának szerzői kivonata: 09.01.01.).
6. ↑ 1 2 3 Feodor Dragan. HT-gráfok: központok, összekapcsolt r-domináció és Steiner fák // Számítás. sci. Moldovai J. (Kishinev) . - 1993. - T. 1 . – S. 64–83 .
7. ↑ Marisa Gutierrez, Oubina. A megfelelő intervallumgráfok és fa-klikk gráfok metrikus jellemzése  // Journal of Graph Theory . - 1996. - T. 21 . – S. 199–205 . - doi : 10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m .
8. ↑ Jayme L. Szwarcfiter, Claudson F. Bornstein. Clique Graphs of Chordal and Path Graphs // SIAM Journal on Discrete Mathematics . - 1994. - T. 7 . – S. 331–336 . - doi : 10.1137/s0895480191223191 .
9. ↑ Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics . - 1998. - T. 11 . – S. 437–455 . - doi : 10.1137/s0895480193253415 .
10. ↑ A maximális szomszédság elrendezésének koncepciója nem triviális, a cikkben (Brandstädt, Dragan, Chepoi, Voloshin, 1998, 440-442. o.) ez 2 oldalt vesz igénybe.
11. ↑ Pablo De Caria, Marisa Gutierrez. Dually Chordal Graphs Minimal Vertex Separators: Properties and Characterizations // Diszkrét alkalmazott matematika . - 2012. - T. 160 . — S. 2627–2635 . - doi : 10.1016/j.dam.2012.02.022 .
12. ↑ Bostjan Bresar. Maximális hiperkockák metszéspontjai // European Journal of Combinatorics . - 2003. - T. \u003d 24 . – S. 195–209 . - doi : 10.1016/s0195-6698(02)00142-7 .
13. ↑ Marina Moscarini. Duplán akkordgráfok, Steiner-fák és összekapcsolt dominancia  // Hálózatok. - 1993. - T. 23 . — 59–69 . - doi : 10.1002/net.3230230108 .
14. ↑ Andreas Brandstädt, Victor Chepoi, Feodor Dragan. Távolság-közelítő fák akkordális és duális akkord gráfokhoz // Journal of Algorithms . - 1999. - T. 30 . – S. 166–184 . - doi : 10.1006/jagm.1998.0962 .
15. ↑ Andreas Brandstädt, Arne Leitert, Dieter Rautenbach. Hatékony uralkodó és éldomináns halmazok grafikonokhoz és hipergráfokhoz // Számítástechnikai előadásjegyzetek . - 2012. - T. 7676 . – S. 267–277 .

Irodalom

• Terry A. McKee, McMorris FR Témák a metszéspontgráf elméletben. — SIAM Monographs on Discrete Mathematics and Applications, 1999.