CliqueConnectedTotal Domination Perfect Graphs

Abstract. In this note we show that the total domination, connected domination and clique domination numbers equal the domination number in every induced subgraph of a graph iff the graph is both C5- and P5-free. For a graph G, the domination number is den

BICAFinalCopy,2pagesFile:totalDomPerfectBICA.tex

Abstract. In this note we show that the total domination, connected domination and clique domination numbers equal the domination number in every induced subgraph of a graph iff the graph is both C5- and P5-free. For a graph G, the domination number is den

Severalauthors[1,2,5]showedthateverysubgraphofGhasadomi-natingcliqueifandonlyifGisP5-andC5-free.CozzensandKelleher[2]alsoprovedthatifGisP5-,C5-andNet-free(wheretheNetisK3withfeet)thenγ(G)=γcl(G).OurresultshowsthattheNetisunnecessary.Theorem.ForagraphG,thefollowingareequivalent:

(1)Gistotaldominationperfect;

(2)γ(H)=γt(H)forallconnectedinducedsubgraphsHwithγ(H)=2;

(3)Gisconnecteddominationperfect;

(4)Giscliquedominationperfect;

(5)everyconnectedinducedsubgraphhasadominatingclique;

(6)GcontainsnoinducedP5orC5.

Itisclearthatanyofthe rst veconditionsimpliescondition(6).That

(6)impliesallofthe rst veisprovenbelow.

Lemma.LetGbeaconnectedgraphwithγ(G)≥2.IfGhasnoinducedP5orC5,thenγ(G)=γt(G)=γc(G)=γcl(G).

Proof.Whileisnothardtoprovefromscratch,wesimplifytheproofbyusingtheresultofZverovich[4].Thatis,sinceGhasnoinducedP5orC5,ithasaminimumdominatingsetDsuchthatG[D]isconnected.

SupposeDisnotaclique.ThentherearetwononadjacentverticesofD,sayuandv,whichhaveacommonneighborc.Butthenomittinguimpliesthereisavertexxadjacentonlytou,andsimilarlyavertexyadjacentonlytov.Thusthe vevertices{u,v,x,y,c}induceaP5orC5,acontradiction.2

References

[1]G.Bacs´oandZs.Tuza,DominatingcliquesinP5-freegraphs.Period.

Math.Hungar.21(1990),303–308.

[2]M.B.CozzensandL.L.Kelleher,Dominatingcliquesingraphs.Discrete

Math.86(1990),101–116.

[3]D.P.SumnerandJ.I.Moore,Dominationperfectgraphs.NoticesAmer.

Math.Soc.26(1979),A-569.

[4]I.E.Zverovich,Perfectconnected-dominantgraphs.Discuss.Math.

GraphTheory23(2003),159–162.

`ZverovichandI.E.`Zverovich,Characterizationofperfect[5]V.E.

dominant-cliquegraphs.Vests¯ Akad.NavukBSSRSer.F¯ z.-Mat.Navuk2(1991),107–109,127.

[6]I.E.ZverovichandV.E.Zverovich,Aninducedsubgraphcharacteriza-

tionofdominationperfectgraphs.J.GraphTheory20(1995),375–395.

2