Dubbel ackordsgraf

Inom det matematiska området för grafteorin är en oriktad graf G dubbelkordal om hypergrafen för dess maximala klick är ett hyperträd . Namnet kommer från det faktum att en graf är kordal om och endast om hypergrafen för dess maximala klick är dualen av ett hyperträd. Ursprungligen definierades dessa grafer av maximal grannskapsordning och har en mängd olika karaktäriseringar. Till skillnad från för ackordsgrafer, är egenskapen att vara dualt ackordal inte ärftlig, dvs inducerade subgrafer i en dual ackordal graf är inte nödvändigtvis dual ackordal (ärftliga dual chordal grafer är exakt de starkt ackordala graferna ), och en dual chordal graf är i allmänhet inte en perfekt graf .

Dual chordal graphs dök upp först under namnet HT-graphs .

Karakteriseringar

Dubbla ackordsgrafer är klickgraferna för ackordsgraferna , dvs skärningsgraferna för maximala klicker av ackordsgrafer.

Följande egenskaper är likvärdiga:

• G har en maximal grannskapsordning.
• Det finns ett spännande träd T av G så att varje maximal klick av G inducerar ett underträd i T .
• Den slutna grannskapshypergrafen N(G) av G är ett hyperträd .
• Den maximala klickhypergrafen för G är ett hyperträd .
• G är 2-sektionsgrafen för ett hyperträd .

Villkoret för hypergrafen för stängt grannskap innebär också att en graf är dubbelkordal om och endast om dess kvadrat är kordal och dess hypergraf för sluten grannskap har Helly- egenskapen .

I De Caria & Gutierrez (2012) karakteriseras dubbla ackordsgrafer i termer av separatoregenskaper. I Brešar (2003) visades det att dubbla kordala grafer är exakt skärningsgraferna för maximala hyperkuber av grafer för acykliska kubiska komplex.

Strukturen och den algoritmiska användningen av dubbla ackordsgrafer ges av Moscarini (1993) . Dessa är grafer som är ackordala och dubbelkorda.

Erkännande

Dubbla ackordsgrafer kan kännas igen i linjär tid, och en maximal grannskapsordning för en dual ackordgraf kan hittas i linjär tid.

Problemens komplexitet

Medan vissa grundläggande problem såsom maximal oberoende uppsättning , maximal klick , färgning och klicktäckning förblir NP-kompletta för grafer med dubbla ackord, är vissa varianter av problemet med minsta dominerande uppsättning och Steiner-trädet effektivt lösbara på grafer med dubbla ackord (men Independent Domination förblir NP -komplett ). Se Brandstädt, Chepoi & Dragan (1999) för användning av dubbla kordala grafegenskaper för trädnyckel, och se Brandstädt, Leitert & Rautenbach (2012) för en linjär tidsalgoritm för effektiv dominans och effektiv kantdomination på dubbla kordala grafer.

Anteckningar

• Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), "The algorithmic use of hypertree structure and maximum neighborhood orderings", Discrete Applied Mathematics , 82 : 43–77, doi : 10.1016/s0166-218x(97)00125-x .
• Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), "Distance approximating trees for chordal and dually chordal graphs", Journal of Algorithms , 30 : 166–184, doi : 10.1006/jagm.1998.0962 .
• Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1993), "Dually Chordal Graphs", Lecture Notes in Computer Science , 790 : 237–251 .
• Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137/s0895480193253415 .
•   Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
• Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs", Lecture Notes in Computer Science , 7676 : 267–277, arXiv : 1207.0953 .
• Brešar, Boštjan (2003), "Skärningsdiagram över maximala hyperkuber", European Journal of Combinatorics , 24 : 195–209, doi : 10.1016/s0195-6698(02)00142-7 .
• De Caria, Pablo; Gutierrez, Marisa (2012), "On Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations", Discrete Applied Mathematics , 160 : 2627–2635, doi : 10.1016/j.dam.2012.02 .
• Dragan, Feodor (1989), Centers of Graphs and the Helly Property (på ryska) , Ph.D. avhandling, Moldova State University, Moldavien .
• Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Platsproblem i grafer och Helly-egenskapen (på ryska)", Diskret matematik. (Moskva) , 4 : 67–73 .
• Dragan, Feodor (1993), "HT-grafer: centra, anslutna r-domination och Steiner-träd", Comput. Sci. J. av Moldavien (Kishinev) , 1 :64–83 .
• Gutierrez, Marisa; Oubina, L. (1996), "Metric Characterizations of proper Interval Graphs and Tree-Clique Graphs", Journal of Graph Theory , 21 : 199–205, doi : 10.1002/(sici)1097-0118(1996202)21 199::aid-jgt9>3.0.co;2-m .
• McKee, Terry A.; McMorris, FR. (1999), Ämnen i intersektionsgrafteori , SIAM-monografier om diskret matematik och tillämpningar .
• Moscarini, Marina (1993), "Double Chordal Graphs, Steiner trees and connected domination", Networks , 23 : 59–69, doi : 10.1002/net.3230230108 .
•   Szwarcfiter, Jayme L.; Bornstein, Claudson F. (1994), "Clique Graphs of Chordal and Path Graphs", SIAM Journal on Discrete Mathematics , 7 : 331–336, CiteSeerX 10.1.1.52.521 , doi : 10.1127/s019154/s019154 .