Dvojitě chordální graf - Dually chordal graph

V matematický oblast teorie grafů, an neorientovaný graf G je dvojitě chordal jestliže hypergraf jeho maximálních klik je a vysoký strom. Název pochází ze skutečnosti, že graf je akordický právě tehdy, když je hypergraf jeho maximálních klik dvojí hyperstrom. Původně byly tyto grafy definovány maximálním uspořádáním sousedství a mají celou řadu různých charakterizací.[1] Na rozdíl od chordálních grafů není vlastnost být duálně chordální dědičná, tj. Indukované podgrafy duálně chordálního grafu nemusí být nutně duální chordální (dědičně duální chordální grafy jsou silně chordální grafy ) a dvojitě chordální graf obecně není a perfektní graf. Pod jménem se nejprve objevily dvojité chordální grafy HT-grafy.[2]

Charakterizace

Dvojitě chordální grafy jsou klikové grafy z chordální grafy,[3] tj. křižovatkové grafy maximálních klik akordových grafů.

Následující vlastnosti jsou ekvivalentní:[4]

  • G má maximální sousedské uspořádání.
  • Je tu klenutý strom T z G tak, aby každá maximální klika G vyvolává podstrom v T.
  • Hypergraf uzavřeného sousedství N (G) z G je vysoký strom.
  • Maximální hypergrafický klik G je vysoký strom.
  • G je dvoudílný graf a vysoký strom.

Podmínka na hypergrafu uzavřeného sousedství také znamená, že graf je duálně chordální právě tehdy, když je jeho čtverec chordální a jeho hypergraf uzavřeného sousedství má Helly vlastnictví.

v De Caria & Gutierrez (2012) duální chordální grafy jsou charakterizovány z hlediska vlastností oddělovače Brešar (2003) ukázalo se, že dvojitě chordální grafy jsou přesně průsečíkové grafy maximálních hyperkrychlí grafů acyklických kubických komplexů.

Struktura a algoritmické využití dvojitě chordálních grafů je dáno vztahem Moscarini (1993). Jedná se o grafy, které jsou chordální a duální chordální.

Uznání

Dvojitě chordální grafy lze rozpoznat v lineárním čase a maximální pořadí sousedství dvojitě chordálního grafu lze najít v lineárním čase.[5]

Složitost problémů

Zatímco některé základní problémy, jako je maximum nezávislá sada, maximum klika, zbarvení a klikový obal zůstat NP-kompletní pro dvojitě chordální grafy některé varianty minima dominující sada problém a Steinerův strom jsou efektivně řešitelné na dvojitě chordálních grafech (ale nezávislá nadvláda zůstává NP-kompletní ).[6] Vidět Brandstädt, Chepoi & Dragan (1999) pro použití vlastností duálně chordálního grafu pro klíče na stromy a viz Brandstädt, Leitert & Rautenbach (2012) pro lineární časový algoritmus efektivní nadvláda a efektivní ovládání hran na dvojitě chordálních grafech.

Poznámky

  1. ^ Brandstädt a kol. (1993); Brandstädt, Chepoi & Dragan (1994); Brandstädt a kol. (1994); Brandstädt a kol. (1998); Brandstädt, Le & Spinrad (1999)
  2. ^ Dragan (1989); Dragan, Prisacaru a Chepoi (1992); Dragan (1993)
  3. ^ Gutierrez & Oubina (1996); Szwarcfiter & Bornstein (1994)
  4. ^ Brandstädt a kol. (1993);Brandstädt, Chepoi & Dragan (1998);Brandstädt a kol. (1998); Dragan, Prisacaru a Chepoi (1992); Dragan (1993)
  5. ^ Brandstädt, Chepoi & Dragan (1998);Dragan (1989)
  6. ^ Brandstädt, Chepoi & Dragan (1998); Dragan, Prisacaru a Chepoi (1992); Dragan (1993)

Reference

  • Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), „Algoritmické využití struktury vysokého stromu a maximálního uspořádání sousedství“, Diskrétní aplikovaná matematika, 82: 43–77, doi:10.1016 / s0166-218x (97) 00125-x.
  • Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), „Stromy přibližující vzdálenost pro chordální a duální chordální grafy“, 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“, Přednášky z informatiky, 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), Třídy grafů: PrůzkumMonografie SIAM o diskrétní matematice a aplikacích, ISBN  0-89871-432-X.
  • Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), „Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs“, Přednášky z informatiky, 7676: 267–277, arXiv:1207.0953.
  • Brešar, Boštjan (2003), „Průnikové grafy maximálních hyperkrychlí“, 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“, Diskrétní aplikovaná matematika, 160: 2627–2635, doi:10.1016 / j.dam.2012.02.022.
  • Dragan, Feodor (1989), Centers of Graphs and the Helly Property (v ruštině), Ph.D. diplomová práce, Moldavská státní univerzita, Moldavsko.
  • Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Problémy s umístěním v grafech a vlastnost Helly (v ruštině)", Diskrétní matematika. (Moskva), 4: 67–73.
  • Dragan, Feodor (1993), „HT-grafy: centra, spojená r-nadvláda a Steinerovy stromy“, Comput. Sci. J. Moldavský (Kishinev), 1: 64–83.
  • Gutierrez, Marisa; Oubina, L. (1996), „Metrické charakterizace správných intervalových grafů a grafů klikajících na stromy“, Journal of Graph Theory, 21: 199–205, doi:10.1002 / (sici) 1097-0118 (199602) 21: 2 <199 :: aid-jgt9> 3.0.co; 2-m.
  • McKee, Terry A .; McMorris, FR. (1999), Témata v teorii křižovatkových grafůMonografie SIAM o diskrétní matematice a aplikacích.
  • Moscarini, Marina (1993), „Double Chordal Graphs, Steiner trees and associated dominance“, Sítě, 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.1137 / s0895480191223191.