Generalized connected domination in graphs
Mekkia Kouider
1and Preben Dahl Vestergaard
2†1Laboratoire de Recherche en Informatique, UMR 8623, Bˆat. 490, Universit´e Paris Sud, 91405 Orsay, France.
E-mail: [email protected]
2Dept. of Mathematics, Aalborg University, Fredrik Bajers Vej 7G, DK–9220 Aalborg Ø, Denmark.
E-mail: [email protected]
received Nov 10, 2003,revised Oct 19, 2005,accepted Jan, 2006.
As a generalization of connected domination in a graphGwe consider domination by sets having at mostkcompo- nents. The orderγck(G)of such a smallest set we relate toγc(G), the order of a smallest connected dominating set.
For a treeTwe give bounds onγck(T)in terms of minimum valency and diameter. For trees the inequalityγkc(T)≤ n−k−1is known to hold, we determine the class of trees, for which equality holds.
Keywords: connected domination, domination, tree Mathematics Subject Classification:05C69
1 Introduction
We consider simple non-oriented graphs. The largest valency inGis denoted by∆(G) = ∆, the smallest byδ(G) =δ. ByPnwe denote a path onnvertices andCndenotes a circuit onnvertices. In a graph a leaforpendant vertex is a vertex of valency one and astemis a vertex adjacent to at least one leaf. In K2each vertex is both a leaf and a stem. The set of leaves in a graphGis denoted byΩ(G). The set of neighbours to a vertexxis denotedN(x). ByK1,kwe denote a star with one central vertex joined tok other vertices. Asubdivided staris a star with a subdivision vertex on each edge. By thecorona graph onH we understand the graphG=H◦K1obtained from the graphHby adding for each vertexxinH one new vertexx0and one new edgexx0. In a corona graph each vertex is either a leaf or a stem adjacent to exactly one leaf. In particular, ifH is a tree, we obtain acorona treeT =H◦K1.
Theeccentricitye(x)of a vertexxis defined bye(x) = max{d(x, y)|y ∈ V(G)}. Thediameter ofGis diam(G)=max{e(x)|x∈ V(G)}. LetD ⊆V(G), thenN(D)is the set of vertices which have a neighbour inD andN[D] is the set of vertices which are inD or have a neighbour inD,N[D] = D∪N(D). A setD ⊆V(G)dominatesGifV(G)⊆N[D], i.e. each vertex not inDis adjacent to a vertex inD. Thedomination numberγ(G)is the cardinality of a smallest dominating set inG.
For a given graphGit is NP-hard to determine its domination numberγ(G), but we can search for for upper bounds as O. Ore started doing about fifty years ago. Also it may be more tractable to restrict the
†Supported by the Danish Natural Science Research Council
1365–8050 c2006 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
minimum dominating set problem to consider only such dominating sets which induce a connected subset ofG, this problem is calledthe minimum connected dominating problemand it is still NP-complete;
In network design theory it is called themaximum leaf spanning tree problem[4], the name will be clear from Section 2 below. We shall study a concept intermediate to the classical and the connected domination, namely by demanding the dominating set to induce at most a given numberkof components, we aim at presenting upper bounds for its orderγkc. Quite likely there is a corresponding problem in network design theory, although we are aware of no reference.
A comprehensive introduction to domination theory is given in [7, 14] and variations are discussed in [5, 13, 15].
Ore [10] proved the inequality below while C. Payan and N. H. Xuong [11], Fink, Jacobsen, Kinch and Roberts [3] determined its extremal graphs.
Proposition 1 LetGbe a connected graph withnvertices,n≥2. Thenγ(G)≤ n
2 and equality holds if and only ifGis either a corona graph or a 4-circuit.
If a treeT hasγ(T) = n
2, thennis even and Proposition 1 implies thatT is a corona tree.
DefinitionFor a positive integerkand a graphGwith at mostkcomponents we define γck(G) = min{|D||D⊆V(G), Dhas at mostkcomponents andDdominatesG}. A setDattaining the minimum above is called aγck-set forG.
Example
γck(Pn) =γck(Cn) =
( n−2k for n≥3k dn
3e for 1≤n≤3k
Fork= 1we have thatγc1is the usual connected domination number,γc1(G) =γc(G).
There exists for every graphGaksuch thatγck(G) =γ(G), e.g.k=|G|.
ForGconnected andk≥1, obviously,γ(G)≤γck(G)≤γc(G).
2 General graphs
LetGbe a connected graph withnvertices andka positive integer. LetF(G)be the maximum number of leaves among all spanning forests ofG, andT(G)be the maximum number of leaves among all spanning trees ofG. With this notation Niemen [9] proved statement (i) below aboutγand Hedetniemi and Laskar [8] generalized it to statement (ii) aboutγc.
(i) γ(G) =n−F(G), (ii) γc(G) =n−T(G).
In the next two theorems we extend these results toγkc.
Theorem 1 Let Gbe a connected graph with nvertices and k a positive integer. LetFk(G) be the maximum number of leaves among all spanning forests ofGwith at mostktrees. Then
γck(G) =n−Fk(G).
Proof: In any spanning forest F with at mostktrees the leaves will be dominated by their stems, so γck(G)≤n− |Ω(F)|and henceγck(G)≤n−Fk(G).
Conversely, letD=D1∪D2∪ · · · ∪Dt, 1≤t≤k, be aγck-set forG. Choose for eachDia spanning treeTi,1 ≤i≤t.For each vertex inV(G)\Dchoose one edge which is incident with a vertex inD.
We have constructed a spanning forestF withtcomponents and at leastn− |D|=n−γck(G)leaves.
ThereforeFk(G)≥n−γck(G)and Theorem 1 is proved. 2
Theorem 2 Letkbe a positive integer andGa connected graph. Then γck(G) = min
γck(Fk)|Fkis a spanning forest ofGwith at mostktrees
= min
γck(T)|T is a spanning tree ofG
Proof: LetFk be a spanning forest ofGwith at mostktrees. Certainlyγck(G) ≤γck(Fk)since a set which dominatesFkalso dominatesG. Conversely, we can inGfind a spanning forestFkwith at mostk components such thatγkc(G) =γck(Fk): As was originally also done in the proofs for (i) and (ii) above we constructFk from aγck-setD = D1∪D2∪ · · · ∪Dt, 1 ≤ t ≤ k, by choosing a spanning tree Ti in each connected subgraphDi and joining each vertex inV(G)\D to precisely one vertex inD.
Obviously,γck(Fk) ≤ |D| =γck(G).This proves the first equality. For the second equality we observe that the first minimum is chosen among a larger set, so thatminγkc(Fk)≤minγck(T),and also that any Fkby addition of edges can produce a treeTwithγck(T)≤γck(Fk). 2
Hartnell and Vestergaard [6] proved the following result.
Proposition 2 Fork≥1andGconnected
γc(G)−2(k−1)≤γck(G)≤γc(G).
From Proposition 2 we can easily derive the following corollary which is a classical result proven by Duchet and Meyniel. [2]
Corollary 3 For any connected graphG,γc(G)≤3γ(G)−2.
Proof: LetGbe a connected graph with domination numberγ(G). Choosek = γ(G), thenγkc(G) = γ(G).Substituting into Proposition 2 above we obtainγc(G)−2(k−1) ≤γ(G)and that proves the
corollary. 2
2.1 Other bounds on γ
ckTheorem 4 For a positive integerkand a connected graphGwith maximum valency∆we have (A) γc(G)≤n−∆and for treesTequality holds if and only ifThas at most one vertex of valency≥3.
(B) γck(G)≤n−(r−1)(δ−2)
3 −2kifGhas diameterr≥3k−1and the minimum valencyδ=δ(G) is at least 3.
(C) IfGis a connected graph with two vertices of valency∆at distancedapart,d≥3,then γck(G)≤n−2(∆−1)−2 min{k−1,d−2
3 }. (1)
(D) Letx∈V(G)have valencyd(x)and eccentricitye(x). Then
γck(G)≤n−d(x)−2 min{k−1,e(x)−2
3 }. (2)
Proof:
(A) LetT be a spanning tree ofGwith∆(T) = ∆(G) = ∆, thenT has at least∆leaves, and hence γc(G)≤γc(T)≤n−∆.
IfT has two vertices of valency≥3, the number of leaves inT will be larger than∆, and we get strict inequality in (A). Clearly, a treeT with exactly one vertex of valency∆≥3has equality in (A) and for∆ = 2, we obtain a pathPnwithγc(Pn) =n−2.
(B) LetP = v1v2v3. . . v3t+u, k ≤ t,0 ≤ u ≤ 2,be a diametrical path inG. The diameter ofT equals the length of P, which is r = 3t+u−1. Fori = 1, . . . , tlet v3i−1 have neighbours v3i−2, v3ionP andaij offP,j= 1, . . . , si si ≥δ−2≥1.InG− {v3iv3i+1|1 ≤i≤k−1}
consider the k−1 disjoint stars with centerv3i−1 and neighbours N(v3i−1), 1 ≤ i ≤ k− 1,and the remaining tree to the right consisting of the pathv3k−2v3k−1v3k. . . v3t+u and leaves v3i−1a3i−1, j= 1, . . . , si, si≥δ−2≥1adjacent to verticesv3i−1, k≤i≤t.
Extend this forest ofktrees to a spanning forestF withktrees inG− {v3iv3i+1|1≤i≤k−1}.
The number of leaves inFis at leastt(δ−2) + 2kand henceγck(G)≤n−t(δ−2)−2k.From t=r+ 1−u
3 ≥ r−1
3 we obtain the desired resultγck(G)≤n−(r−1)(δ−2)
3 −2k.
C Letv1, vsbe two vertices inGwith maximum valency,d(v1) =d(vs) = ∆, and letP =v1v2. . . vs be a shortestv1vs-path,s= 3t+ 1 +u, t≥1,0≤u≤2.
Case 1,t≥k−1: In G− {v3i−1v3i|1 ≤ i ≤ k−2} we extend thek trees listed below to a spanning forestFofG,
1. The star consisting ofv1joined to all its neighbours, 2. thek−2paths of length twov3iv3i+1v3i+2,1≤i≤k−2,
3. the pathv3k−3v3k−2. . . vstogether with all∆−1neighbours ofvsoutside ofP. F will have at least2(∆−1) + 2(k−1)leaves.
Case 2,t≤k−2: s = 3t+ 1 +u, d = d(v1, vs) = s−1 = 3t+u, t−1 = d−u 3 −1 ≥ d−2
3 −1. As before, we can find a spanning forestFofGwhose number of leaves is at least 2∆ + 2(t−1)≥2(∆−1) + 2d−2
3 and consequentlyγck(G)≤n−2(∆−1)−2d−2 3 . The proof of D is similar.
2
3 Trees
For trees Hartnell and Vestergaard [6] found
Proposition 3 Letkbe a positive integer andT a tree with |V(T)| = n, n ≥2k+ 1.Thenγck(T) ≤ n−k−1.
This inequality is best possible. Fork= 1the extremal trees are pathsPnand fork ≥2extremal trees will be described in the following Theorem 5.
A treeTis of type A if it contains a vertexx0such thatT−x0is a forest of treesT1, T2, . . . , Tα, α≥1, such that each treeTi is a corona tree andx0is joined to a stem in each of the treesTi,1 ≤i≤α.We note that a subdivision of a star is a tree of type A.
A treeT is of type B if it contains a path uvw such that T − {u, v, w} is a forest of corona trees T1, T2, . . . , Ts, Ts+1,, . . . , Tα, α ≥ 2,1 ≤ s < α and u is joined to a stem in each of the trees T1, T2, . . . , Ts,whilewis joined to a stem in each of the treesTs+1,, . . . , Tα.
Proposition 4 below was proven by Randerath and Volkmann [12], Baogen, Cockayne, Haynes, Hedet- niemi and Shangchao [1].
Proposition 4 IfT is a tree with n vertices, n odd, andγ(T) =bn
2cthenTis a tree of type A or B.
We shall now determine the trees extremal for Proposition 3.
Theorem 5 Letk ≥2be a positive integer andT a tree withnvertices,n ≥2k+ 1. Thenγkc(T) = n−k−1if and only if one of cases (i)-(iii) below occur.
(i) k=n−1
2 ,γck(T) =γ(T) =n−1
2 andTis of type A or B.
(ii) k=n−2
2 ,γck(T) =γ(T) =n
2 andTis a corona tree.
(iii) k = n−3
2 ,γck(T) = n+ 1
2 ,γ(T) = n−1
2 andT is a starK1,k+1with a subdvision vertex on each edge.
Proof: First, letk ≥2and a treeT of ordernbe given such thatn≥2k+ 1andγck(T) =n−k−1.
We shall prove thatTis as described in one of the three cases (i)-(iii).
We note in passing that
Remark 1 γ(T)≤kimpliesγck(T) =γ(T), and that likewiseγck(T)≤kimpliesγck(T) =γ(T).
Ifn= 2k+ 1, or equivalentlyk= n−1
2 , we have by assumptionγck(T) =n−k−1 =kand, as just observed above, that implies that alsoγ(T) =k. Sincek=bn
2cwe obtain from Proposition 4 thatT is a tree of type A or B, so Case (i) occurs.
Ifn = 2k+ 2, or equivalentlyk = n−2
2 we have by assumption γck(T) = n−k−1 = k+ 1.
Certainlyγ(T)≤γck(T), but ifγ(T)≤kthen we should have thatγck(T) =γ(T)≤kin contradiction
toγck(T) =k+ 1, thereforeγ(T) =k+ 1 = n
2. From Proposition 1 we obtain thatT is a corona tree, i.e. Case (ii) occurs.
We may now assumen≥2k+ 3, and we shall prove that, in fact,nequals2k+ 3and that Case (iii) occurs.
Letv1v2. . . vαbe a longest path inT. Sinceγck(T) =n−k−1≥k+ 2≥4,Tis neither a star nor a bistar and thereforeα≥ 5. We must havedT(v2) = 2, because otherwisedT(v2)≥3and we could fromT delete three leaves adjacent tov2, ifdT(v2)≥4, and in casedT(v2) = 3we could deletev2and its two adjacent leaves. In both cases we would obtain a treeT0of ordern−3≥2(k−1) + 1which by Proposition 3 hasγck−1(T0)≤(n−3)−(k−1)−1≤n−k−3. Addingv2to aγck−1(T0)-set we would obtainγck(T)≤n−k−2, a contradiction. ThereforedT(v2) = 2.
The vertexv3cannot be adjacent to two leavescandd, say, because, then the treeT0=T−{v1, v2, c, d}
would have ordern−4≥2(k−1) + 1. Thus Proposition 3 gives thatγck−1(T0)≤(n−4)−(k−1)−1
≤n−k−4and addingv2, v3to aγck−1(T0)-set we would obtainγck(T)≤n−k−2, a contradiction.
Sov3can be adjacent to at most one leaf. The casedT(v3) = 3andv3adjacent to one leafccan similarly be seen to be impossible by consideringT0=T\ {v1, v2, v3, c}.
On the other handdT(v3)≥3, for assumedT(v3) = 2, thenT0 =T \ {v1, v2, v3}hasγk−1c (T0)≤ n−k−3and addition ofv2to aγck−1(T0)-set would giveγck(T)≤n−k−2, a contradiction.
Assume therefore thatv3besidesv2andv4is adjacent to precisely one leafcand to at least one further vertexa, whereahas valency two and is adjacent to the leafb. ThenT0 =T \ {v1, v2, a, b}has order n−4≥2(k−1) + 1and Proposition 3 gives that (3)γck−1(T0)≤(n−4)−(k−1)−1≤n−k−4. In T0the vertexcis a leaf and as anyγck−1-set forT0must contain one of{v3, c}, we may assume it contains v3. Addition of{v2, a}to aγck−1(T0)-set now gives the contradictionγck(T)≤n−k−2.
Assume finally thatv3has no leaf but besidesv2andv4is adjacent toa1, a2, . . . , at,t≥1, where each aihas valency two and is adjacent to the leafbi,1≤i≤t.
We havek−t ≥ 1becauseV(T)\ {v1, b1, b2, . . . , bt, vα}is a connected subgraph withn−t−2 vertices which dominateT, so thatn−k−1 =γck(T)≤n−t−2givingk−t≥1. Consider the tree T0=T\ {v1, v2, a1, a2, . . . , b1, b2, . . . , bt, v3}of ordern−2t−3.
Ifn−2t−3≥2(k−t) + 1we obtain by Proposition 3 thatγck−t(T0)≤(n−2t−3)−(k−t)−1≤ n−k−t−4, and by addition of thet+2vertices{v2, v3, a1, a2, . . . , at}, (which span a connected subgraph ofT), to aγck−t(T0)-set we obtainγck(T)≤n−k−2, a contradiction. So we haven−2t−3≤2(k−t) and now|V(T0)|=n−2t−3 ≤2(k−t)impliesγ(T0)≤ |V(T0)|
2 ≤k−twhich by remark 1 gives thatγck−t(T0) = γ(T0)and hence addition of thet+ 2vertices{v2, v3, a1, a2, . . . , at}to aγck−t(T0)- set (having at mostk−t vertices) givesγck−t+1(T) ≤ k+ 2. We now haven−k−1 = γck(T) ≤ γck−t+1(T)≤k+ 2givingn≤2k+ 3, so the assumptionn≥2k+ 3impliesn= 2k+ 3. By hypothesis γck(T) =k+ 2and we haveγ(T)≤k+ 1by Proposition 1.
Thusγ(T) =k+ 1, (because otherwiseγkc(T) = γ(T)< k+ 2), and anyγ(T)-set must consist of k+ 1isolated vertices. Asγ(T) =bn
2cthe treeT by Proposition 4 is of type A or B. ButT cannot be of type B, for assumeT is of type B. ThenT consists of a 3-path ,uvw, with each of its ends joined to stems of corona trees, and since we have just seen thatv3, vα−2are neither stems nor leaves, they must play the role ofu, w, soα= 7andTconsists of two subdivided stars centered respectively atu=v3andw=v5
and a vertexv=v4joined touandw. Among itsγ-sets this treeT has one with two adjacent vertices, namelyv2andv3, a contradiction, soTis of type A .
Using, in analogy tov2, v3, thatdT(vα−1) = 2and thatvα−2is not a stem, we get thatα= 5andT is a subdivided star so that (iii) occurs.
Conversely, it is easy to see that if (i), (ii) or (iii) holds thenγck(T) =γ(T) =n−k+ 1. This proves
Theorem 5. 2
References
[1] X. Baogen, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi, Z. Shangchao: Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000), 1-10.
[2] P. Duchet, H. Meyniel:On Hadwiger’s number and stability number, Ann. Discr. Math. 13 (1982), 71-74.
[3] J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts:On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), 287-293.
[4] S. Guha, S. Khuller: Approximation algorithms for connected dominating sets, Algorithmica 20 (1998), 374-387.
[5] B.L. Hartnell, P.D. Vestergaard: Partitions and domination in graphs, J. of Combin. Math. and Combin. Comput. 46 (2003), 113-128.
[6] B.L. Hartnell, P.D. Vestergaard:Dominating sets with at mostkcomponents, Ars Combin. 74 (2005), 223-229.
[7] Teresa W. Haynes, Stephen T. Hedetniemi, Peter J. Slater: Fundamentals of domination in graphs.
Marcel Dekker, New York 1998.
[8] S.T. Hedetniemi, R.C. Laskar: Connected domination in graphs, B. Bollabas, ed.: Graph Theory and Combinatorics.Academic Press, London, 1984.
[9] J. Niemen: Two bounds for the domination number of a graph, J. Inst. Math. Applics. 13 (1974), 183-187.
[10] O. Ore: Theory of Graphs, Amer. Soc. Colloq. Publ. vol. 38. Amer. Math. Soc., Providence, RI 1962.
[11] C. Payan and N. H. Xuong:Domination-balanced graphsJ. of Graph Theory 6 (1982), 23-32.
[12] B. Randerath, L. Volkmann,Characterization of graphs with equal domination and covering num- ber, Discrete Math. 191 (1998), 159-169.
[13] Zs. Tuza, P.D. Vestergaard: Domination in partitioned graphs. Discuss. Math. Graph Theory. 22 (2002), 199-210.
[14] E. Sampathkumar: Domination parameters of a graphpp. 271-299 in Teresa W. Haynes, Stephen T. Hedetniemi, Peter J. Slater, eds.:Domination in Graphs, Advanced Topics.Marcel Dekker, New York 1998.
[15] S. Seager:Partition domination of graphs of minimum degree two.Congr. Numer. 132 (1998), 85-91.
