Chordal bipartit diagram - Chordal bipartite graph

I det matematiska området för grafteori är en ackordal bipartitgraf en bipartitgraf B  = ( X , Y , E ) där varje cykel med längd minst 6 i B har ett ackord , dvs en kant som förbinder två hörn som är ett avstånd> 1 från varandra i cykeln. Ett bättre namn skulle vara svagt ackord och bipartit eftersom ackordbipartitdiagram i allmänhet inte är ackordal som den inducerade cykeln med längd 4 visar.

Karaktäriseringar

Chordal bipartitdiagram har olika karakteriseringar när det gäller perfekta eliminationsordningar , hypergrafer och matriser . De är nära besläktade med starkt ackorddiagram . Per definition har ackordbipartitdiagram en förbjuden karaktärisering av undergrafer som grafer som inte innehåller någon inducerad cykel med längd 3 eller längd minst 5 (så kallade hål) som en inducerad subgraf . Således är en graf G ackordbipartit om och bara om G är triangelfri och hålfri. I Golumbic (1980) nämns två andra karakteriseringar: B är chordal bipartite om och bara om varje minimal kantseparator inducerar en fullständig bipartit subgraph i B om och bara om varje inducerad subgraph är perfekt eliminering bipartite.

Martin Farber har visat: En graf är starkt ackordal om och endast om tvåpartsincidensdiagrammet för dess klickhypergraf är ackordbipartit.

En liknande karaktärisering gäller för hypergrafen för stängda grannskap: En graf är starkt ackordal om och endast om tvåpartsincidensdiagrammet för dess stängda grannskapshypergraf är ackordbipartit.

Ett annat resultat som Elias Dahlhaus hittat är: En bipartitgraf B  = ( X , Y , E ) är ackordbipartit om och bara om den delade grafen som resulterar från att göra X till en klick är starkt ackordal.

En bipartitgraf B  = ( X , Y , E ) är ackordbipartit om och endast om varje inducerad subgraf av B har en maximal X- närbildsordning och en maximal Y-grannskapsordning.

Olika resultat beskriver förhållandet mellan ackordbipartitdiagram och totalt balanserade stadshypergrafer av bipartitdiagram.

En karakterisering av ackordbipartitdiagram i termer av skärningsdiagram relaterade till hypergrafer ges i.

En bipartitgraf är ackordbipartit om och bara om dess angränsningsmatris är helt balanserad om och endast om angränsningsmatrisen är gammafri.

Erkännande

Ackordala bipartitdiagram kan kännas igen i tiden O (min ( n 2 , ( n + m ) log n )) för en graf med n hörn och m kanter.

Komplexitet av problem

Olika problem som Hamiltonian-cykeln, Steiner-trädet och Effektiv dominans förblir NP-kompletta på ackordbipartitdiagram.

Olika andra problem som kan lösas effektivt för tvåpartsdiagram kan lösas mer effektivt för ackordbipartitdiagram som diskuteras i

Relaterade diagramklasser

Varje ackordbipartitdiagram är ett moduldiagram . De ackordala bipartitdiagrammen innehåller de fullständiga bipartitdiagrammen och de tvåpartsavstånds -ärftliga graferna .

Anteckningar

Referenser

  • Brandstädt, Andreas (1991), "Klasser av tvåpartsdiagram relaterade till ackorddiagram", Diskret tillämpad matematik , 32 : 51–60, doi : 10.1016 / 0166-218x (91) 90023-p.
  • 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), Grafklasser: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Dragan, Feodor; Voloshin, Vitaly (1996), "Incidensdiagram för biacykliska hypergrafer", Diskret tillämpad matematik , 68 : 259–266, doi : 10.1016 / 0166-218x (95) 00070-8.
  • Farber, M. (1983), "Karaktäriseringar av starkt ackorddiagram", Diskret matematik , 43 (2–3): 173–189, doi : 10.1016 / 0012-365X (83) 90154-1.
  • Golumbic, Martin Charles (1980), algoritmisk grafteori och perfekta grafer , Academic Press, ISBN 0-12-289260-7.
  • Huang, Jing (2006), "Representationskarakteriseringar av ackordbipartitdiagram", Journal of Combinatorial Theory, serie B , 96 (5): 673–683, doi : 10.1016 / j.jctb.2006.01.001.
  • Lu, Chin Lung; Tang, Chuan Yi (2002), "Viktad effektiv dominans på några perfekta grafer", Diskret tillämpad matematik , 117 : 163–182, doi : 10.1016 / s0166-218x (01) 00184-6.
  • Lubiw, A. (1987), "Dubbel lexikalisk ordning av matriser", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137 / 0216057.
  • Müller, Haiko (1996), "Hamilton circuits in chordal bipartite charts", Discrete Mathematics , 156 : 291–298, doi : 10.1016 / 0012-365x (95) 00057-4.
  • Müller, Haiko; Brandstädt, Andreas (1987), "The NP-completeeness of Steiner Tree and Dominating Set for chordal bipartite charts", Theoretical Computer Science , 53 : 257-265, doi : 10.1016 / 0304-3975 (87) 90067-3.
  • Paige, R .; Tarjan, RE (1987), "Three partition refinement algorithms", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137 / 0216062.
  • Spinrad, Jeremy (1993), "Dubbel lexikal ordning av täta 0-1 matriser", Information Processing Letters , 45 (2): 229-235, doi : 10.1016 / 0020-0190 (93) 90209-R.
  • Spinrad, Jeremy (2003), Effektiva grafrepresentationer , Fields Institute Monographs, American Mathematical Society, ISBN 0-8218-2815-0.