Minimum Dominating Tree Problem for Graphs

LIN Hao,LIN Lan

(1.School of Science,Henan University of Technology,Zhengzhou 450001,China;2.School of Electronics and Information Engineering,Tongji University,Shanghai 200092,China)

Minimum Dominating Tree Problem for Graphs

LIN Hao1,LIN Lan2

(1.School of Science,Henan University of Technology,Zhengzhou 450001,China;2.School of Electronics and Information Engineering,Tongji University,Shanghai 200092,China)

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

network optimization;minimum dominating tree;special graphs;exact evaluation

§1. Introduction

With application background in construction of communication networks,the minimum spanning tree problem in combinatorial optimization is to fi nd a spanning tree T in a weighted connected graph G to minimize the weight w(T)ofthe tree.This problem has been extensively studied in the literature[1-3].A famous generalization is the Steiner tree problem,in which the required subtree T connects several given vertices of G(see[2-3]).Similarly,the optimal dominating tree problem also comes up with applications in network constructions:Given a weighted connected graph G,we are asked to find a subtree T which contains at least one neighbor ofeach vertex(namely,V(T)constitutes a dominating set)such that the weight w(T) of the tree is minimized.As a matter of fact,a large scale communication network often consists of two parts:the principal part is a dominating tree which connects to the neighbor set of each terminaland the secondary part is the set of branch-lines between the terminals and the principal part.In particular,in the wireless senor network(see[4]),many senors(vertices) are scattered on the plane and people want to build a backbone network to controlthese senors.Similar situations appear in transportation system and supply-demand system.The optimal dominating tree problem is concerned with this kind of construction of principal networks.In our previous paper[5],we prove this problem is NP-hard and present a branch-and-bound algorithm.

The present paper studies the case of un-weighted graphs,i.e.,each edge has weight 1.We can formulate the problem as follows.Given a connected simple graph G=(V,E),where V is the vertex set and E is the edge set,the problem is to find a subtree T=(V′,E′)such that each vertex in VV′is adjacent to a vertex in V′and the number|V′|of vertices of T is minimized.Since V′is a dominating set of G,this problem is called the minimum dominating tree problem.A related problem in graph theory is the dominating set problem,in which one is asked to find a minimum dominating set of G.This is an active topic in recent years(see, e.g.,[6]).

This also reminds us the so-called maximum leaf spanning tree problem as follows

Given a connected graph G,the problem is to find a spanning tree T of G such that the number of leaves(degree-1 vertices)is maximized.We have the following equivalence.

Theorem 1.1 Given a connected graph G,the minimum dominating tree problem of G is equivalent to the maximum leaf spanning tree problem of G.

Proof For a dominating tree T=(V′,E′),we can obtain a spanning tree by adding the vertices of VV′as leaves.Conversely,for a spanning tree,we can obtain a dominating tree by deleting all leaves.Furthermore,minimizing|V′|is equivalent to maximizing|VV′|. Hence the minimum dominating tree problem is equivalent to the maximum leaf spanning tree problem,as required.

First,[3]pointed out that the maximum leafspanning tree problem is NP-hard(see problem [ND2]in P206).Later,a number of articles[7-9]were concentrated on the approximation algorithms.In our present paper,we are concerned with a graph-theoretic parameter m d t(G), the vertex number of the minimum dominating tree of G.The main goal is to determine this parameter for some typicalclasses of graphs.

We shall follow the terminology and notation of[1].

§2. Interval Graphs

The class ofintervalgraphs is wellknown in perfect graphs(see[10]).A graph G is called an intervalgraph ifits vertices can be put into one-to-one correspondence with a set ofintervals in the real line such that two vertices are adjacent if and only if their corresponding intervals have nonempty intersection.So the vertices of G may be represented by a set of intervals[ai,bi]for i=1,2,···,n.The following is a characterization of intervalgraphs.

Lemma 2.1[10]A graph G is an interval graph if and only if the maximal cliques of G can be linearly ordered such that,for every vertex v of G,the maximal cliques containing v occur consecutively.

In more detail,all maximal cliques of G constitute the path decomposition[11]as follows

All maximal cliques of G can be ordered as a sequence(X1,X2,···,Xr)satisfying

(2)For any edge uv∈E(G),there exists an i with 1≤i≤r,such that{u,v}?Xi;

(3)For any i＜j＜k,Xi∩Xk?Xj.

Here,(3)implies that all maximal cliques containing a vertex v occur consecutively.We assume in the sequel that the interval representation{[ai,bi]:1≤ i≤ n}and the path decomposition{Xi:1≤i≤r}for an interval graph G are given in advance.The purpose of this section is to determine the minimum dominating tree number m d t(G)for interval graphs.

Lemma 2.2 Let G be any graph with diameter D(G).Then m d t(G)≥D(G)?1.

Proof Suppose that D(G)=dG(u,v),where u,v∈V(G)and dG(u,v)is the distance between u and v in G.Let T be a minimum dominating tree.Then u,v must be dominated by two vertices u′,v′in T respectively.Let P′=(u′,···,v′)be the unique path between u′,v′in T.Then we obtain a path P=(u,u′,···,v′,v)in G.Hence m d t(G)+1=|V(T)|+1≥|V(P′)|+1=|V(P)|?1≥dG(u,v)=D(G).This completes the proof.

Theorem 2.3 If G is an intervalgraph,then m d t(G)=D(G)?1.

Proof Let G be an interval graph with vertex set V(G)={v1,v2,···,vn}.For each vertex v∈V(G),the corresponding intervalis denoted by[a(v),b(v)],where a(v)is the left-end and b(v)is the right-end ofthe interval.Moreover,allmaximalcliques of G constitute the path decomposition(X1,X2,···,Xr).We proceed to construct a dominating tree T as follows.

First,assume that v1is the vertex whose interval has the smallest right-end b(v1)= min{b(vi):1≤ i≤ n}(if there is a tie,we choose the smallest left-end a(v1)).Then for any two neighbors of v1,the corresponding intervals have nonempty intersection(as they must have the right-end b(v1)of v1in common).Thus v1belongs to a unique maximalclique,namely X1,which consists of v1and allits neighbors.

Symmetrically,we assume that vnis the vertex whose interval has the largest left-end a(vn)=max{a(vi):1≤i≤n}(if there is a tie,we choose the largest right-end b(vn)).Then any two neighbors of vnare adjacent(as their intervals must have the left-end a(vn)of vnin common).Thus vnbelongs to a unique maximal clique,namely Xr.

Then we take a shortest path P=(v1,x1,x2,···,xt,vn)between v1and vnin G.Since x1is adjacent to v1,we see that x1∈X1.By Lemma 2.1,the maximalcliques containing x1occur consecutively.So we may suppose that the maximalcliques containing x1are X1,X2,···,Xi1in order.Let Y1=X1∪X2∪···∪Xi1.Then a vertex y is adjacent to x1if and only if y∈Y1. We proceed inductively.Suppose that xkand its neighbor set Ykare given(k≥1).As xk+1is adjacent to xk,we have xk+1∈Yk.Without loss ofgenerality,we may assume that xk+1∈Xik(if xk+1∈Xjwith j＜ik,the proof below is still valid).By Lemma 2.1 again,the maximal cliques containing xk+1occur consecutively,say they are Xik,Xik+1,···,Xik+1.Then theneighbor set of xk+1is Yk+1=Xik∪Xik+1∪···∪Xik+1.Set k:=k+1 and repeat the above procedure until we reach xtwhich is adjacent to vn.In this way,we obtain a path P′=(x1,x2,···,xt)which dominates all vertices inHence P′is a dominating tree of G.

Furthermore,as P=(v1,x1,x2,···,xt,vn)is a shortest path from v1to vnin G,we conclude that|V(P)|=dG(v1,vn)+1.Besides,for any two vertices x,y∈V(G),suppose that x∈Xi,y∈Xj.Then a shortest path from x to y can use a part of P.Thus dG(x,y)≤dG(v1,vn) and so P is a diameter path of G.Therefore P′is a dominating tree with vertex number D(G)?1.By Lemma 2.2,P′is a minimum dominating tree of G and m d t(G)=D(G)?1. The proof is complete.

By this theorem,for an interval graph G,the minimum dominating tree is a path and the maximum leaf tree is a“caterpillar”.Here,a tree is called a caterpillar ifit yields a path when all leaves are deleted.

§3.Powers of Paths and Cycles

For a graph G,the k-th power Gkof G is defined as the graph with the same vertex set of G that two distinct vertices u and v are adjacent in Gkif and only if their distance in G is at most k.In particular,if the vertex set of a path Pnon n vertices is V(Pn)={v1,v2,···,vn},then the edge set of the k-th power of PnisSimilarly,if the vertex set of a cycle Cnon n vertices is V(Cn)={v1,v2,···,vn},then the edge set of the k-th power of Cnis={vivj:min{|i?j|,n?|i?j|}≤k}.For an edgeif |i?j|≤k,then we say that e covers the path(vi,vi+1,···,vj)of Cn;if n?|i?j|≤k,then we say that e covers the path(vj,vj+1,···,vn,v1,···,vi)of Cn.

Conversely,we show that a dominating tree ofcorresponds to a dominating tree ofwith the same vertex number.Let T be a dominating tree ofwith vertex set V(T)= {vi1,vi2,···,vil},where 1≤i1＜i2＜···＜il≤n.We distinguish two cases as follows.

(1)There exists an edge of Cnwhich is not covered by any edge of T.Without loss of generality,we may assume this edge is vnv1.We construct afromby deleting all edges ofthat cover vnv1.Then T is a dominating tree of this

(2)Every edge of Cnis covered by an edge of T.Then we can see that|ih?ih+1|≤k for1≤h≤l?1,since there is an edge of T that covers the path from vihto vih+1.So we can construct a dominating path P=(vi1,vi2,···,vil)ofwith|V(P)|=|V(T)|.Furthermore, this P is a dominating tree ofwith the same vertex number as T.

In summary,we set up a correspondence between the dominating trees ofand the dominating trees ofwith the same vertex number.ThereforeThis completes the proof.

§4.Halin Graphs

Clearly,for a wheel Wn,its center is a minimum dominating tree and so mdt(Wn)=1. As a generalization of wheels,there is a well-known class of 3-connected graphs,called Halin graphs[1].A graph G is called a Halin graph if it can be drawn in the plane as a tree T0without degree-2 vertices together with a cycle C passing through the leaves of T.

Theorem 4.1 For any Halin graph G=(V,E),m d t(G)=2|V|?|E|?1.

Proof Let T0and C be the tree and the cycle in the definition.Then T0is a spanning tree of G and E(C)is the edge set ofthe co-tree of T0.For any spanning tree T,let l(T)denote the number of leaves of T.We first show that T0is a spanning tree with the maximum l(T). For this,we use induction on the number r of non-leaf vertices of T0.When r=1,G is a wheel with a center(or“hub”)h.Meanwhile,the vertices of C can be denoted by x1,x2,···,xn?1. For any other spanning tree T/=T0,at least one xiis not a leafin T(where hxi∈E(T)).Hence l(T)≤n?1=l(T0).Suppose that r＞1 and the assertion holds for smaller r.For the tree T0, let y be the second vertex of a diameter path of T0.Then y must be a non-leaf vertex and allits neighbors but one are leaves.Now let x1,x2,···,xkbe the leaves adjacent to y.We denote by W the subgraph of G induced by{y,x1,x2,···,xk}.Note that W is also a subgraph of a wheel.For any other spanning tree T1/=T0,when restricting to the subgraph W,the leaf number of T1is not greater than that of T0(by the argument for wheels).So we change the part of T1in W to coincide with T0and obtain another spanning tree T2.Then l(T1)≤l(T2). Now we contract W to a single vertex w.Then the resulting graph G′is still a Halin graph. Letandbe the corresponding spanning trees of T0and T2respectively.By the induction hypothesis,we haveTherefore l(T2)≤ l(T0)and thus l(T1)≤ l(T2)≤ l(T0) holds,completing the induction.

Note that T0is a spanning tree and E(C)is the edge set of the co-tree of G.The edge number of the co-treeμ(G)=|E|?|V|+1 is called the cyclic rank of G.So l(T0)=|E(C)|= |E|?|V|+1.Finally we conclude that the vertex number of the minimum dominating tree is m d t(G)=|V|?l(T0)=|V|?(|E|?|V|+1)=2|V|?|E|?1.The proof is complete.

§5.Outer-planar Graphs

The outer-planar graphs are a special class of planar graphs.We consider a 2-connected outer-planar graph G,that is,it has a plane embedding such that all vertices are lying on theboundary C of the outer face.Apart from the edges on cycle C,the remaining edges are the chords of the cycle.As G is simple,we do not consider multiple edges.

The dual graph of a plane embedding of a planar graph G is defined as follows:each face(region)is corresponding to a vertex and two vertices are joined by an edge if and only if two faces have a common edge in their boundaries.When we delete the vertex ofouter face(and the incident edges)in the dualgraph,the resulting graph is called the weak-dualgraph,denoted by G?.Figure 1 shows an outer-planar graph G and its weak-dual graph G?.We claim that the weak-dual graph of an outer-planar graph is a tree.If not,there is a cycle in the weakdual graph G?and so this cycle surrounds a vertex of graph G,which cannot be contained in the boundary of the outer face.This leads to a contradiction to the definition of outer-planar graphs.

An outer-planar graph G is said to be serialif(1)its weak-dualgraph G?is a path;(2)the boundary of each face and the outer-boundary C have precisely one section(an edge or a path) in common(see Figure 1).

Proposition 5.1 For a serial outer-planar graph G,if the boundary of every face is a triangle(which is a maximalouter-planar graph),then m d t(G)=D(G)?1.

Proof In this case,each maximalclique of G is a triangle and allthese maximalcliques can be ordered in a sequence satisfying the conditions of path decomposition.By Lemma 2.1, G is an interval graph.Further by Theorem 2.3,the result follows.

Figure 1 A Serial Outer-planar Graph and Its Weak Dual Graph

We generalize this result to a general serial outer-planar graph G,in which the boundary of a face is not necessarily a triangle,namely,this boundary intersects C at a path of length at least two(see faces abb′a′and bcc′e in Figure 1).

A face of G corresponding to a leaf of G?is called a terminal face of G.So G contains two terminal faces.The boundary of a terminal face f consists of two parts:a section of cycle C(a path),denoted by Cfand a chord of C.This path Cfmust have length at least two(for otherwise multiple edges occur,contradicting the assumption of simple graphs)and thus contains degree-2 vertices.On the other hand,if the boundary of a non-terminal face f is not a triangle,then it must contain a section of cycle C(a path)with length at least two,which is also denoted by Cf(the other part ofthe boundary consists oftwo chords).In both cases,wewill call these paths Cfspecial boundaries.

When a spanning tree of graph G is constructed,we must break all cycles in G,namely, delete one edge from the boundary of each face.In order to get as many leaves as possible in the special boundaries Cf,the following properties should be satisfied

(1)If Cfhas length two,say Cf=uxv with x being a degree-2 vertex,then either ux or xv is deleted and x becomes a leaf.

(2)If Cfhas length at least three,say Cf=ux···yv with x,···,y being degree-2 vertices, then one of the edges in x···y is deleted and two ends of this edge become leaves.

Algorithm for Serial Outer-planar Graphs

Input A serial outer-planar graph G.

Output A spanning tree T of G with maximum number of leaves.

Step 1 For a terminal face f,if the special boundary Cfhas length at least three,say Cf=ux···yv,then x···y is contracted into a single vertex.Moreover,ifthe specialboundary Cfof a non-terminal face f has length at least two,say Cf=ux···yv,then it is removed by deleting the internal vertices x,···,y.

Step 2 Let f1and f2be the two terminalfaces.Find a shortest path P from the internal vertex of Cf1to the internal vertex of Cf2.Take E1=E(P).

Step 3 Let L be the set of vertices dominated by V(P),i.e.,L={x∈V(G)V(P): there is a y∈V(P)such that xy is a chord}.Let E2be the set of chords chosen by:for each x∈L,a chord xy is chosen such that y∈V(P).

Step 4 For the terminal face f that Cf=ux···yv has length at least three and x···y is contracted into a single vertex in Step 1,we restore the special boundary Cfand obtain two leaves by deleting one of the edges in x···y.Moreover,for the non-terminal face f that the special boundary Cfhas length at least two and the internal vertices are deleted in Step 1,we restore the special boundary Cf.If Cf=uxv has length two,then we delete either ux or xv; especially,we delete ux whenever u(rather than v)is a leaf of the constructed tree so far.If Cf=ux···yv has length at least three,then we obtain two leaves by deleting one of the edges in x···y.Let E3be the set of adding edges of C in this step.

Step 5 Return the spanning tree T with edge set E(T)=E1∪E2∪E3.

For example,in the graph of Figure 1,we first take the shortest path abcd from f1to f2and set E1={ab,bc,cd}.Then we take the set ofchords E2={bb′,bb′′,cc′}.For the special boundaries,we take E3={ab,a′b′,be}.

Proposition 5.2 For a serialouter-planar graph G,the above algorithm provides a spanning tree T with the maximum number of leaves.

Proof We first consider the vertices in the special boundaries.For a terminal face f,Cfis a section of cycle C,which must have length at least two.If Cfhas length two,then the boundary of face f is a triangle and we do nothing for it.If Cfhas length at least three,thenthere willbe two leaves in it and we may do this in the last step.Nevertheless,we may contract the internal vertices to make its boundary to be a triangle at the beginning.Moreover,for the non-terminal face f that the special boundary Cf=ux···yv has length at least two,we claim that there exists a spanning tree T with the maximum number of leaves such that T does not contain the whole path Cf.Suppose,to the contrary,that T contains the whole Cf. Then apart from Cf,the remaining boundary of f consists of two chords,one of which is not contained in T(for otherwise there is a cycle in T).Thus,we may construct a new spanning tree T′by deleting one edge of Cfand adding the chord not in T.It is easy to see that the leaf number of T′is not less than that of T(as at least one more leaf occur in Cfand at most one leafis lost when adding the chord).This shows the claim.By this claim,we can delete the internal vertices of Cffirst in Step 1 and then restore them in Step 4.

After the treatment of Step 1,the boundary of each face is a triangle and this reduces to the case of intervalgraph G′.Step 2 and Step 3 comprise the algorithm for finding a spanning tree with maximum leafnumber ofintervalgraph G′.Finally,in Step 4 we make the leafnumber in special boundaries Cfas large as possible.Therefore the spanning tree T constructed by the algorithm is one of maximum leaf number.This completes the proof.

By the above algorithm,we obtain a maximum leaf spanning tree T and thus obtain a minimum dominating tree by deleting the leaves.

[1]BONDY J A,MURTY U S R.Graph Theory[M].Berlin:Springer,2008.

[2]PAPADIMITRIOU C H,STEIGLITZ K.CombinatorialOptimization:Algorithms and Complexity[M].New Jersey:Prentice-Hall,1982.

[3]GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the NP-Completeness[M].New York:Freman,1979.

[4]SHANG Wei-ping,YAO F,WAN P.On minimum m-connected k-dominating set problem in unit disc graphs[J].J of Combinatorial Optimization,2008,16(2):99-106.

[5]LIN Hao,LIN Lan.Optimal dominating tree problem in networks[J].Systems Engineering-Theory and Practice,2006,26(5):83-87.

[6]SONG Xiao-xin,WANGXiao-feng.Roman dominating number and dominating number ofa tree[J].Chinese Quarterly Journal of Mathematics,2006,21(3):385-367.

[7]FUJIE T.The maximum-leaf spanning tree problem:formulations and facets[J].Networks,2004,43(4): 212-223.

[8]LI P C,TOULOUSE M.Variations of maximum leaf spanning tree problem for bipartite graphs[J].Information Processing Letters,2006,97(40):129-132.

[9]LU H,RAVIR.Approximating maximum leafspanning trees in almost linear time[J].J of Algorithms,1998, 29:132-141.

[10]GOLUMBIC M.Algorithmic Graph Theory and Perfect Graphs[M].New York:Academic Press,1980.

[11]GUSTEDT J.On the pathwidth of chordal graphs[J].Discrete Appl Math,1993,45(3):233-248.

tion:05C35,05C69,90C35

1002–0462(2014)01–0001–08

Chin.Quart.J.of Math. 2014,29(1):1—8

date:2013-03-01

Supported by NNSF of China(11101383,61373106)

Biography:LIN Hao(1974-),male,native of Taishan,Guangdong,an associate professor of Henan University of Technology,M.S.D.,engages in network optimization.

CLC number:O157.5 Document code:A