Paired Domination Number of Outerplanar Graphs∗

ZHUANG Wei,YANG Weihua

(1.School of Applied Mathematics,Xiamen University of Technology,Xiamen Fujian 361024,China;2.College of Mathematics,Taiyuan University of Technology,Taiyuan Shanxi 030024,China)

Abstract: In this paper,we prove that outerplanar graphs with diameter two and three have bounded paired domination number.This implies that the paired domination number of such graphs can be determined in polynomial time.Furthermore,we characterize all outerplanar graphs with diameter two.On the other hand,we also give examples of outerplanar graphs of diameter at least four,having arbitrarily large paired domination numbers.

Key words:paired domination;outerplanar graphs;diameter

0 Introduction

The literature on the subject of domination parameters in graphs has been surveyed through 1997 and detailed in the two books[1,2].In this paper we continue the study of paired domination in graphs first introduced by Haynes et al.[3]as a model for assigning backups to guards for security purposes,and which is now very well studied[4–6].

Amatchingin a graphGis a set of independent edges inG.Aperfect matching MinGis a matching such that every vertex ofGis incident with an edge ofM.Apaired dominating set,abbreviated PDS,ofGis a setSof vertices ofGsuch that every vertex is adjacent to some vertex inSand the subgraph induced byScontains a perfect matching(not necessarily induced).Every graph without isolated vertices has a paired dominating set,since the end-vertices of any maximal matching form such a set.Thepaired domination numberofG,denoted by γpr(G),is the minimum cardinality of a paired dominating set.Clearly,the paired domination number of a graph without isolated vertices is even.

For a graphsG,ifu∈V(G),N(u)denotes the set of neighbors ofu,d(u)=|N(u)|,and letN[u]=N(u)∪{u}.Ifxandyare two vertices ofG,then anxy-pathis simply a path with endsxandy,anddistancebetweenxandy,d(x,y),is the length of a shortestxy-path,where the length of the path is the number of edges.LetS⊂V(G)andx∈S.We say thatxhave aprivate neighbor(with respect toS)if there is a vertex inV(G)Swhose only neighbor inSisx.SupposeX,Y⊆V(G).We say thatX dominates Yif every vertex ofYis adjacent to at least one vertex ofX.

A planar graphGis said to beouterplanarifGcan be embedded in the plane in such a way that all vertices are incident with a common face.From this it is easy to see that say 2-connected outerplanar graphs has a Hamilton cycle.In our proofs,it is necessary to work with an embedding of the outerplanar graph,and it is important to note that the paired domination number of the graph is independent of the embedding.Any terminology not defined here follows that of[7].

1 Main results

The problem of determining the paired domination number of a graph with diameter one is uninteresting,since such graphs are precisely the complete graphs,and hence have paired domination number two.Diameter at least two graphs provide a more interesting study.First,we will briefly consider outerplanar graphs with diameter four.

Consider the star onk+1 vertices,k≥1,and subdivide each edge once.The resulting outerplanar graph on 2k+1 vertices has diameter four.It is easy to see that the paired domination number of this graph is 2k.It follows that there exist outerplanar graphs with diameter four whose paired domination number is arbitrarily large.Similarly,we can also construct some outerplanar graphs with diametert(t>4)whose paired domination number are arbitrarily large.

From this discussion,we see that the only remaining cases in which the paired domination number can be bounded by a constant is that of outerplanar graphs with diameter two and three.

In contrast,it is easy to bound the paired domination number for outerplanar graphs of diameter two.

Theorem 1 IfGis an outerplanar graph with diameter two,then γpr(G)=2 except for the cycleC5which has paired domination number 4.

Proof Suppose thatGis an outerplanar graph with diameter two.IfGhas a cut vertexu,then{u,v}is a paired dominating set,whichv∈N(u).Otherwise,Gis a 2-connected and we can embedGso that a Hamilton cycle,H,bounds the outer face,and the edges not inHare chords that lie in the interior ofH.IfHhas no chords,thenGis simply a cycle of length at most five,and clearly,γpr(G)=2 except for the cycle isC5.IfHhas chords,then the end vertices of any such chord are a cutset inG.SinceGhas diameter two,the cutset is a paired dominating set,and so γpr(G)=2.

One Friday evening I came home from work to find a big beautiful German shepherd on our doorstep. This wonderful strong animal gave every indication that he intended to enter the house and make it his home. I, however, was wary4. Where did this obviously well-cared-for dog come from? Was it safe to let the children play with a strange dog? Even though he seemed gentle, he still was powerful and commanded respect. The children took an instant liking5 to German and begged me to let him in. I agreed to let him sleep in the basement until the next day, when we could inquire around the neighborhood for his owner. That night I slept peacefully for the first time in many weeks.

Based on the above theorem,we may characterize all outerplanar graphs with diameter two.To begin with,we characterize the outerplanar graphs with diameter two and paired domination number two.LetK4−e,H5,F5,H6andF6denote the five graphs shown in Fig 1.LetAdenote the family of graphs that can be obtained from a cycleCnby joining some vertex onCnto all other vertices.A graph in the familyAis illustrated in Fig 2.LetBbe a family of graphs,a graphGbelongs toBif and only ifGcontains a cut vertexvof degree|V(G)|−1,and any componentTofG−vinduces a pathx1x2···xt(t≥ 2)or an isolated vertex,wherex1,x2,···,xtare adjacent tovin cyclic order(as in Fig 3).

Fig 1 K4−e,H5,F5,H6 and F6

Fig 2 a graph in A

Fig 3 a graph in B

Theorem 2 A graphGis an outerplanar graph with diameter two if and only ifG∈{C4,C5,H5,F5,H6,F6}∪A∪B.

Proof The sufficiency is true clearly.So we prove the necessity.By Theorem 1,We only need to discuss the case γpr(G)=2.Clearly,|G|≥ 4.Suppose thatGis an outerplanar graph with diameter two and paired domination number two,and furthermore,thatGis 2-connected.It follows thatGcan be embedded in such a way that a Hamilton cycleHbounds the outer face,and the edges not inHare chords that lie in the interior ofH.Since γpr(G)=2,then there are a set{u,v}dominates the other vertices,whereuvis an edge or a chord ofH.

Ifuvis an edge ofH,letuandvare the neighbors ofuandvinH,respectively,whereuv,vu.Ifuv∈E(G),thenGC4orK4−e(Note thatK4−ebelongs toA).If not,note thatuvE(G)oruvE(G),sayuvE(G).Since there exists a path of length 2 fromutov,eitheruv∈E(G)or there exists a vertexwsuchuw,wv∈E(H).In the first case,it is easy to see thatG∈A.In the second case,GH5orF5.

Ifuvis an chord ofH,verticesuandvbreakHinto twouv-paths.We call the path that goes in the clockwise direction fromutovtheuv-segmentofH,and the other path thevu-segmentofH.Assume that there aretinternal vertices on thevu-segmentofH.Now we consider the case thatt≥ 2.Letuandvare the neighbors ofuandvonvu-segmentofH,respectively,anduandvare the neighbors ofuandvonuv-segmentofH,respectively.Note thatuvE(G)oruvE(G),sayuvE(G).Since there exists a path of length 2 fromvtou,souvis a chord or an edge ofH.

Suppose thatuvis a chord ofH,thenvis adjacent to all internal vertices ofuv-segmentofH.Note thatd(u,v)=2 anduvis a chord ofH,we have thatuv∈E(H).This implies thatG∈A.Next,we consider the case thatuvis an edge ofH.Ift=2,thenGH5orF5.Ift≥3,letv1be a neighbor ofvonvu-segmentofHandv1v.Since there exists a path of length 2 fromutov1anduvE(G),we have thatuv1∈E(G)orvv1∈E(G).Note thatd(u,v)=2,we conclude thatG∈{H6,F6}∪A.

Ift=1,by a similar argument as above,we also have thatG∈{H5,F5,H6,F6}∪A.

Now suppose thatGis not 2-connected,letvbe a cut vertex inG,and letTbe a component ofG−vwhich is not an isolated vertex,whereV(T)={x1,x2,···,xt}.Without loss of generality,we may assume that an embedding ofGas an outerplanar graph has verticesx1,x2,···,xtin cyclic order,adjacent tov.Since all vertices ofGlie on a common face,all vertices ofTinduce a pathx1x2···xt.That is,GB.

Simultaneously,we have that the following corollary.

Corollary 1 LetGbe an outerplanar graph of ordern,Ghas diameter two if and only if∆(G)=n−1 orGis isomorphic to one ofC4,C5,H5,F5,H6,F6.

Next,for outerplanar graphs with diameter three,we will show that the paired domination number is two or four.The graph which is constructed from a cycleC6by joining two vertices with distance three and the cycleC7shows that the lower bound and the upper bound are both best possible,respectively.

Lemma 1 SupposeGis a graph with diameter three,S⊂V(G)be a cutset,andA,Ba partition ofV(G)Sinto nonempty subsets such that there are no edges joining vertices ofAwith vertices ofB.ThenSdominates eitherAorB.

Proof A path froma∈Atob∈Bmust contain at least one vertex fromS.If neitherAnorBis dominated byS,then there exist verticesx∈Aandy∈Bwithd(x,y)≥4,a contradiction.

Theorem 3 IfGis an outerplanar graph with diameter three,then γpr(G)=2 or 4.

Proof Suppose thatGis an outerplanar graph with diameter three,and furthermore,thatGis 2-connected.It follows thatGcan be embedded in such a way that a Hamilton cycleHbounds the outer face,and the edges not inHare chords that lie in the interior ofH.IfGhas no chords,thenGis a cycle of length at most seven,and thus has paired domination number at most four.Now we assume thatHhas at least one chord.

Suppose thatxyis a chord ofH.VerticesxandybreakHinto twoxy-paths.We call the path that goes in the clockwise direction fromxtoythexy-segmentofH,and the other path theyx-segmentofH.First suppose thatHhas precisely one chord,xy.Then{x,y}is a cutset,and sinceGhas diameter three,by lemma 1,we know that this set dominates either thexy-segment ofHoryx-segment ofH;without loss of generality,suppose that thexy-segment is dominated.Since there are no other chords,thexy-segment is a path of length two or three,and sinceGhas diameter three,theyx-segment is a path of length four or five,according as thexy-segment has length three or two.Therefore,Hhas length at most seven,and we can easily find a vertex setSof cardinality at most four that dominatesG,whereG[S]contains a perfect matching.

We may now assume thatHhas at least two chords.Choose a vertex cut of size two,{a,b},that dominates a maximum number of vertices(this set may or may not correspond to the ends of a chord ofH).SinceGhas diameter three,this set dominates one segment ofH;without loss of generality,theba-segment ofHis dominated by{a,b}.Consider theab-segment ofH.If there are no chords with both ends on theab-segment ofH,then there are at most four internal vertices on the path.Then by choosinga,b,and the two internal vertices on theab-segment ofHwhich are adjacent toaandb,respectively,we obtain a paired dominating set of cardinality four.

If there is chord with both ends on theab-segment ofH,then choose a vertex cut of size two,{c,d},with both vertices in theab-segment ofH,and such that any other vertex cut of size two with both vertices in theab-segment ofHhas at least one vertex in thecd-segment ofH(where thecd-segment ofHis part of theab-segment ofH).

Fig 4 a subgraph of G which contains two vertex cuts{a,b}and{b,c}

First suppose thata,b,canddare not all distinct vertices;without loss of generality,we may assume thatb=d,and thatGcontains the subgraph in Fig 4.By our choice of{c,b}={c,d},any vertex on theac-segment ofHdoes not form a cutset withb,and henceacmust be an edge(acmay be an edge ofHor a chord ofH).By the way that{a,b}was chosen,{c,b}must dominate thecb-segment ofH.Now consider the edgeac.Ifacis a chord ofH,then it mustdominate theac-segment ofH,otherwise it contradicts our choice of{a,b}.Ifacis not a chord,then it is an edge ofH,and there no internal vertices in theac-segment ofH.In either case,{a,b,c}is a dominating set.Ifbhas a private neighborp(with respect to the set{a,b,c}),then{a,b,c,p}is a paired dominating set ofG;If not,then{a,c}is a paired dominating set ofG.

Fig 5 a subgraph of G which contains two vertex cuts{a,b}and{c,d}

We now consider the case wherea,b,canddare distinct vertices(The choice of{c,d}implies that neitheradnorbcis an edge ofG).Without loss of generality,we may assume thatGcontains the subgraph shown in Fig 5.By the way that{a,b}and{c,d}were chosen,we know that{a,b}dominates theba-segment ofHand that{c,d}dominates thecd-segment ofH.Furthermore,acandbdmust both be edges.As before,ifacis a chord ofH,then it dominates theac-segment ofH;otherwiseacis an edge ofHand there are no internal vertices in theac-segment ofH.Similarly,ifbdis a chord ofH,then it dominates thedb-segment ofH;otherwisebdis an edge ofHand there are no internal vertices in thedb-segment ofH.Therefore,{a,b,c,d}is a dominating set ofG.And clearly,it is also a paired dominating set ofG.This completes the proof in the case whereGis 2-connected.

Now suppose there is a cut vertexvinG.By lemma 1,there is a partition ofV(G){v}into setsAandBsuch thatvdominates eitherAorB.Without loss of generality,we may assume the vertexvdominatesA,and thata∈A.Clearly,every vertex inBis distance at most two fromv;letB=B1∪B2,whereB1contains the vertices ofBthat are adjacent tov,andB2contains the vertices ofBdistance two fromv.

Choose a minimum cardinality subsetSofB1such thatSdominatesB2.ThenS∪{v}dominatesG.We claim that|S|≤ 2.Suppose that|S|≥ 3,lets1,s2,s3be three vertices ofS.By the minimality ofS,there exist verticesx1,x2,x3∈B2such thatxiis a private neighbor ofsi,i=1,2,3.Without loss of generality,we may assume that an embedding ofGas an outerplanar graph has verticesa,s1,s2,s3in cyclic order,adjacent tov.Since all the vertices ofGlie on a common face,there is no way to obtain a path of length at most three betweenx1andx3without violating the private neighbor condition.Therefore,|S|≤2.If|S|=1,thenS∪{v}is a paired dominating set inGof cardinality two.If|S|=2,letS={s1,s2},by choosing the set{v,s1,s2,t}(wheretis one of private neighbors ofs2,with respect to the set{v}∪S),we obtain a paired dominating set of cardinality four.