Printer Friendly

Recurrence among trees with most numerous efficient dominating sets.

A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization of all maximum trees is given. Their structure has recurring aspects with period 7. Moreover, the number of efficient dominating sets in maximum n-vertex trees is determined and is exponential. Also the number of maximum n-vertex trees is shown to be bounded below by an increasing exponential function in n.

Mathematics Subject Classification: 05C69, 05C05, 05C35, 05C75, 05A15

Keywords: counting, efficient domination, structural characterization, trees

1 Introduction

Our aim is to maximize the number of efficient dominating sets among n-vertex trees. This is a sequel to our article [4]. Paper [4] presents characterizations of trees with largest or smallest (and still large) numbers of dominating sets. Trees without any efficient dominating set exist. Determining whether or not a graph has an efficient dominating set is an NP-complete problem, see [2, 8]. A constructive characterization of trees which have an efficient dominating set can be found in [2]. That is why we concentrate on characterizing trees with the largest number of efficient dominating sets. There are several papers devoted to characterizing graphs with maximal numbers of specified substructures. Erdos is credited for raising a question which is answered in the pioneering paper [9] of 1965 by Moon and Moser on maximizing the number of cliques among n-vertex graphs. There is a series of publications on the related problem of maximizing the number of maximal independent sets among different graphs, and trees also are considered [16, 10, 17]. At the beginning of 1980s Tomescu, when dealing with cliques in specialized hypergraphs, studied [14] number-theoretical problem of maximizing a constrained product of binomial coefficients, the simplest possible subcase of the problem being solved by Moon and Moser [9]. The second author, when dealing with maximizing the number of maximum path-factors among trees, arrived independently [12] at another subcase of Tomescu's problem. A solution to Tomescu's problem was found by Schinzel and Skupien, cf. [13].

Given a graph G, a vertex set S [[subset].bar] V (G) is called a dominating set of G if any vertex of G either is in S or has a neighbor in S. Following Bange et al. [1], a dominating set D of G is called an EDS (efficient dominating set) if the distance between any two members of D is at least three in G. Bange, Barkauskas and Slater [2] proved the following result.

Proposition 1 If G has an efficient dominating set, then the cardinality of any efficient dominating set equals the domination number of G. In particular, all efficient dominating sets have the same cardinality.

The number of efficient dominating sets in oriented graphs, and in particular, oriented trees was studied [3, 11].

Observation 1 Given any dominating set D of a graph G, if v [member of] V (G) then either v [member of] D or a neighbor of v is in D. If D is any EDS and v [not member of] D then exactly one neighbor of v is in D.

Let [T.sub.n] be the class of unlabeled trees of order n, where isomorphic trees are considered identical. In what follows T stands for a tree with vertex set V (T), |T| denotes the cardinality of V (T). A leaf (or pendant vertex) and a B-vertex (or branch vertex) are vertices of degree at most one and at least three, respectively. Let B(T) and b(T) denote respectively the set and number of B-vertices in T. A twig in T is a nontrivial path joining a leaf of T to the closest vertex in T which is not of degree two. Hence the number of twigs, say [theta]_(T), either is the number of leaves if b(T) > 0 or is one less than the number of leaves if T is a path (whether trivial or not). Given an i [member of] {0, 1, 2} and x [member of] B(T), let [[tau].sub.i] (x) be the number of twigs attached to x with lengths congruent to i modulo 3.

Let T have a B-vertex. Consider the subtree obtained by ungluing all twigs from T (i.e., by deleting all non-B-vertices of twigs together with all incident edges). Then every pendant vertex x of the subtree is called a PB-vertex (or a pendant B-vertex) of T. Let PB(T) stand for the set of pendant branch vertices in T.

Let q(T) denote the number of all efficient dominating sets of T. Given a positive integer n, let [??](n) denote the maximum of q(T) over all trees T on n vertices, n = |T|. Then each n-vertex tree such that q(T) = [??](n) is called a maximum tree.

We shall characterize all maximum trees T on n vertices. If n [greater than or equal to] 9 then the structure of T is quite easy to describe. Namely, each maximum tree T has uniquely defined number b of branch vertices, b = b(n). Branch vertices induce a subtree, and all remaining vertices of T are on twigs of length two only. To define b = b(n) for any n [greater than or equal to] 39 or odd n [greater than or equal to] 33, let [??] = [n+2/7]. Then b is an integer such that b = n (mod 2) and b [member of] {[??]; [??] - 1}. Note that if 7|n and n [greater than or equal to] 35 then b = n/7. Moreover, b(n) = b for all n = 7b + 2s with s = -1, 0, 1, ..., 5 provided that b [greater than or equal to] 5. Thus s, which determines some structural aspects, is a periodic function of n with period 7. Our main result is that any tree on b vertices is a subtree induced by branch vertices of an n-vertex maximum tree with n such that b = b(n). Additionally we give a detailed specification of the following estimation. The number of maximum trees on n vertices is exponential in n because, for n [greater than or equal to] 39, it is at least the number |[T.sub.b]| of all trees on b vertices with b = b(n) ~ n/7 as n [right arrow] [infinity], the lower bound being attained if 7|n and n [greater than or equal to] 35. We determine [??](n), and [??](n) is exponential in n, too.

EDS' and maximum trees can possibly be used to design computer or communication networks, facility and guard locations, surveillance systems, interference-free transmission and/or cooperation, cf. [7, p. 891].

2 Preliminaries

Using Proposition 1 we can see that in case of a nontrivial path [P.sub.n] (n [greater than or equal to] 2) each efficient dominating set of [P.sub.n] contains no endvertex, both endvertices and exactly one endvertex depending on whether n is congruent modulo 3 to 0, 1, 2, respectively. Hence the number of efficient dominating sets in [P.sub.n] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Assume that T is a tree with a twig P of length 3 or more. Let z be a leaf of T in P and wxyz a subpath in P. Then wxyz is called a terminal subtwig in T. The transformation T [??] T - {x,y,z} is called a 3-reduction of T. Recursive repetition of a 3-reduction eventually gives a subtree of T, say T, which does not have any twig of length 3 or more. Call [bar.T] to be the 3-trim of T.

Proposition 2 Any 3-reduction T [??] T' does not change the number of EDS', i.e., q(T') = q(T).

Proof: Given a leaf z of T such that wxyz is a terminal subtwig in T, let T' = T - {x,y,z}. Due to Observation 1 and the definition of EDS, if D is an EDS of T then {z,w} [[subset].bar] D or, if T [not equal to] [P.sub.4], {y,u} [[subset].bar] D where u is a neighbor of w in T'. Hence, for each D, D - {z,y} is an EDS of T'. Conversely, if D' is any EDS of T' then, due to Observation 1 (with v = w in T'), D' is uniquely augmentable to an EDS of T. Therefore D [??] D - {z,y} is a bijection from EDS' in T onto those in T'.

Corollary 1 q([bar.T]) = q(T) if [bar.T] is the 3-trim of T. 2

Recall that for x [member of] B(T), [[tau].sub.i](x) is the number of twigs of length congruent to i modulo 3, i = 0, 1, 2, twigs being attached to x.

Proposition 3 Let T be a tree with exactly one branch vertex x. Let [[tau].sub.i] = [[tau].sub.i](x). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 2 Let T be an n-vertex tree with b(T) = 1, n [greater than or equal to] 7, n [not equal to] 8, and with q(T) being the largest possible number of EDS'. Then [[tau].sub.1] = 0 and q(T) = [[tau].sub.2] [greater than or equal to] 3 where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

whence all twigs are of length 2 but one of length 3 for even n only.

3 Useful recursive relations

We are going to present a recurrence relations for the number q(T): Assume that b(T) [greater than or equal to] 2 and x is a PB-vertex. Then there exists a unique vertex a(x) which is the neighbor of x on a path from x to another B-vertex in T. The vertex a(x) is said to be the attachment vertex of x. Let T - * x be the tree obtained from T by deleting the PB-vertex x together with all twigs attached to x. Call T - *x to be tree T minus star at x. Let [T.sub.a(x)+i] stand for a tree obtained from T - * x by adding a new y-a (x) path of length i = 0, 1, 2, where y = a(x) if i = 0. Let q[(T.sub.a(x)+I]; y) be the count of all efficient dominating sets that contain y. The following result is easily seen due to Observation 1.

Lemma 1 Let b(T) [greater than or equal to] 2 and [[tau].sub.0] = 0 at all B-vertices of T. Assume that x [member of] PB(T), a(x) is the attachment vertex of x, and = [[tau].sub.i](x) for i = 1; 2. Let y be the endvertex of path y-a(x) of length j = 0, 1, 2 in the tree [T.sub.a(x)+j]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

One can easily check that orders of trees [T.sub.a(x)+1] and [T.sub.a(x)+2] involved in Lemma 1 are at most |T| - 2. Using some of the above results and inspecting the list of small trees in Harary [5] gives the following.

Proposition 4 All trees T on n vertices with n [less than or equal to] 10 which are maximum, i.e., with q(T) = [??](|T|), are listed in Fig. 1, T being unique if n [not equal to] 4, 6, 8.

The symbol S(G) (which appears in Fig. 1) stands for subdivision graph of G. Recall that S(G) results in inserting a new vertex of degree 2 into each edge of G.

A vertex x of a tree T is called EDS-avoided if x does not belong to any efficient dominating set of T.

Proposition 5 Each tree of order n [greater than or equal to] 3 has an EDS-avoided vertex. In fact, each vertex at distance 2 from a leaf is EDS-avoided. 2

Lemma 2 Let b(T) [greater than or equal to] 2, x [member of] PB(T), [[tau].sub.1](x) = [[tau].sub.0](x) = 0, and [[tau].sub.2](x) [greater than or equal to] 2. Then q(T) [less than or equal to] [[tau].sub.2](x) q(T - *x),

where T minus star at x is involved, and equality is true if and only if a(x), the attachment vertex of x, is EDS-avoided in T - *x (i.e., q([T.sub.a(x)+0], y) = 0).

Proof: On applying Lemma 1 we have

q(T) = q([T.sub.a(x)+0], y) + [[tau].sub.2](x) q([T.sub.a(x)+2], y). (2)

Due to Observation 1, one can see that q(T - *x) = q([T.sub.a(x)+0], y) + q([T.sub.a(x)+2], y): Hence, by (2),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where equality holds whenever q([T.sub.a(x)+0], y) = 0, which ends the proof.

[FIGURE 1 OMITTED]

4 Preliminary maximization

Let [T.sup.2] be the family of unlabeled trees T such that b(T) [greater than or equal to] 1 with both [[tau].sub.1] = [[tau].sub.0] = 0 and [[tau].sub.2] [greater than or equal to] 2 at each B-vertex. Moreover, all [theta](T) twigs are of length two and contain all degree-2 vertices of T. Let [T.sup.2.sub.n] be the subclass comprising n-vertex elements of [T.sup.2]. Let T [member of] [T.sup.2] and let b = b(T), [theta] = [theta](T). It follows that T includes a subtree, say [T.sub.b], on b vertices. If b = 1 then [theta] [greater than or equal to] 3, |T| = 1 + 2[theta] [greater than or equal to] 7 whence |T| is odd and T = S([K.sub.1,[theta]]), the unique subdivision of the star [K.sub.1,[theta]]. If b [greater than or equal to] 2 then [theta] [greater than or equal to] 2b and |T| = b + 2[theta] [greater than or equal to] 5b. Hence

[n.sub.b] := min{|T|: T [member of] [T.sup.2], b(T) = b} = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Proposition 6 Let T [member of] [T.sup.2.sub.n]. Then branch vertices induce a subtree <B(T)> of T and

n = |T| = b(T) + 2 [theta](T), (4)

b(T) [equivalent to] |T| (mod 2), (5)

q(T) = [theta](T) if b(T) = 1, (6)

7 [less than or equal to] |T| [not equal to] 8, (7)

[theta](T) = [summation over (x[member of]B(T))] [greater than or equal to] max{2b(T)),3} [greater than or equal to] 3. (8)

The following observation complements Proposition 5.

Proposition 7 If T [member of] [T.sup.2] then EDS-avoided vertices in T coincide with B-vertices. From (6), Lemma 2 and Proposition 7, for T [member of] [T.sup.2], we get the following.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Observation 2 The RHS (right-hand side) of (9) determines the corresponding tree T up to the distribution of twigs in the following sense.

Consider a finite product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of integers [t.sub.i] [greater than or equal to] 2 where |I| [greater than or equal to] 1. Let b = |I|, the number of factors in the product, [theta] = [[summation].sub.i[member of]I] [t.sub.i], the sum of factors, and let n = b + 2[theta]. Let [T.sub.b] be any tree on b vertices with arbitrarily assigned mutually distinct labels [x.sub.i], i [member of] I. Let T be a tree obtained from [T.sub.b] by attaching [t.sub.i] twigs of length two to the vertex [x.sub.i] for each i [member of] I. Hence [[tau].sub.2]([x.sub.i]) = [t.sub.i], T [member of] [T.sup.2.sub.n], and q(T) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [t.sub.i].

For n [greater than or equal to] [n.sub.b], let [T.sup.2.sub.n] (b) comprise T [member of] [T.sup.2.sub.n] with b(T) = b and such that q(T) is the largest possible.

Lemma 3 If T [member of] [T.sup.2.sub.n] (b) and b > 1 then the numbers [[tau].sub.2] at any two B-vertices of T differ by at most one.

Proof: If values of [[tau].sub.2] are m and k such that m > k + 1 then mk < (m - 1)(k + 1) whence making the values closer one to another (by moving a twig from one B-vertex to the other) increases the value of q.

Corollary 3 If T [member of] [T.sup.2.sub.n] (b) and [theta] = [theta](T) then

[theta] = (n - b)/2 by (4) and (5), q(T) = [[theta]/b].sup.b-([theta] mod b)] [[theta]/b].sup.[theta] mod b (10)

due to (8), (9), and Lemma 3. 2

Let [q.sub.2] (n) denote the maximum of q(T) among n-vertex trees T [member of] [T.sup.2] where n = |T| satisfies requirement (7). Let [T.sup.2,max] = {T [member of] [T.sup.2] : q(T) = [q.sub.2](|T|)}, each element of [T.sup.2,max] is called a [T.sup.2]-maximum tree. Let [T.sup.2,max.sub.n] stand for the subset of [T.sup.2,max] comprising n-vertex elements.

Let [b.sub.2](n) be the largest b(T) among [T.sup.2]-maximum n-vertex trees T, T [member of] [T.sup.2,max.sub.n]. Small trees T [member of] [T.sup.2.sub.n] have the unique b(T), either 1 or 2 (as determined by the parity of n), and then [q.sub.2](n) can be obtained from (9). Namely (see Tab. 1),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then T [member of] [T.sup.2,max.sub.n] is unique.

For larger n, if n is fixed and T ranges over [T.sup.2.sub.n] then, by (3) and (5), b = b(T) ranges over all natural numbers [less than or equal to] n/5 such that b = n (mod 2). Then [q.sub.2](n) can be found by inspection using Corollary 3. Namely, for each admissible value of b, we find [theta] and next q(T). Then [q.sub.2](n) is the largest of numbers q(T) thus found. Moreover, the corresponding b equals [b.sub.2](n).

Let RHS stand for the product on the right-hand side of formula (10). Then b(T) is the sum of two exponents of which one can be 0, [theta] is the sum of the single factors in RHS, cf. (8). Consequently, formula (4) gives n.

The results of search for two largest products, L < R, where both L and R are RHS corresponding to a fixed n, are presented in Tab. 2 for some values of n as stated. Consequently, for those n, R = [q.sub.2](n) whence the corresponding b = [b.sub.2](n).

Tab. 2 serves two purposes. Firstly, it suggests that the function b2 weakly increases when restricted to n of either parity. Moreover, each value of b displayed within parentheses in Tab. 2 is first attained at the corresponding underlined value of n so that b = [b.sub.2](n) for that n and all larger n which are smaller than the next underlined one. Secondly, if L is displayed at n = k then no [q.sub.2](n) with n [greater than or equal to] k includes L as a subproduct. Otherwise replacing L in [q.sub.2](n) by the corresponding R = [q.sub.2](k) gives q(T) as in formula (9) where |T| = n, T [member of] [T.sup.2.sub.n], and q(T) > [q.sub.2](n), a contradiction.

Maximum product R = [q.sub.2](n) and the corresponding b = [b.sub.2](n) for each admissible n [less than or equal to] 40 are presented in Tab. 3.

Theorem 1 For each n such that n = 7 or 9 [less than or equal to] n [less than or equal to] 40, Tab. 3 presents both the number [q.sub.2](n) of efficient dominating sets and the number b = [b.sub.2](n) of B-vertices in any T [member of] [T.sup.2,max.sub.n].

5 Large trees

For a T [member of] [T.sup.2,max.sub.n],

[m.sub.k] := |}x [member of] B(T): [[tau].sub.2](x) = k}|: (11)

Proposition 8 Let T [member of] [T.sup.2,max.sub.n] where n [greater than or equal to] 39 or n = 33, 35, 37. Then [m.sub.k] = 0 unless k [member of] {2, 3, 4}. Hence b(T) = [m.sub.2] + [m.sub.3] + [m.sub.4]. Additionally, [m.sub.2][m.sub.4] = 0, [m.sub.2] [less than or equal to] 1, [m.sub.4] [less than or equal to] 5, and [m.sub.3] is unbounded. The stated bounds on n (odd n [greater than or equal to] 33 or any n [greater than or equal to] 39) are sharp because [m.sub.2] = 2 if n = 31 or 38.

Proof: Tab. 1 and products L together with the corresponding values of n in Tab. 2 are chosen so as to show that, for a T [member of] [T.sup.2,max.sub.n], all the factors [[tau].sub.2 = k [not equal to] 3 have bounded multiplicity [m.sub.k]. Namely, [m.sub.k] = 0 for k = 7, 8, 9 by Tab. 2 and for k = 7+r [greater than or equal to] 10 because then 7+r < [3.sup.2]r with n = 15+2r and b [member of] {1, 3}. Furthermore, products L at n = 24, 26 show that [m.sub.6] = 0 if n is not too small. Actually [m.sub.6] = 0 for n [greater than or equal to] 14 and the bound is tight because [q.sub.2](13) = 6 (Tab. 1). Similarly, products L at n = 38, 47 and R at n = 29 show that [m.sub.5] = 0 for n [greater than or equal to] 30. Analogously, products L at n = 45, 52 show that [m.sub.2] [less than or equal to] 1 for large n. On the other hand, products R at n = 47, 54 show that [m.sub.2] = 1 is possible for large n. Products R at n = 45, 52 show that [m.sub.4] [greater than or equal to] 5 is allowed for large n but, due to L at n = 54, [m.sub.4] = 5 at most. Lemma 3 implies that [m.sub.2][m.sub.4] = 0. The value [m.sub.2] = 2 in R for n = 31 and 38 shows sharpness of the stated bounds for n. 2

A tree T is called a large tree if its order |T| [greater than or equal to] 39 or |T| = 33, 35, 37.

Theorem 2 Let T be a large tree from [T.sup.2,max.sub.n], b = b(T), and s = [m.sub.4] - [m.sub.2] whence s = -1, 0, ... 5, s = -1 if [m.sub.2] = 1, otherwise s = [m.sub.4]. Then s uniquely depends on n (Tab. 4),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

b = [b.sub.2](n) = n -2s / 7(13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

Proof: By Proposition 8, [m.sub.3] = b-[m.sub.2]-[m.sub.4]. Hence, by (4) and (8), n = b+2[theta] = b+4[m.sub.2]+6[m.sub.3]+8[m.sub.4] = 7b + 2([m.sub.4]-[m.sub.2]) = 7b + 2s whence (13). Consequently 7|n - 2s. Hence, by Proposition 8, we get Tab. 4 whence (12) and (14) follow. On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [m.sub.2][m.sub.4] = 0, which implies (15).

Theorem 3 For n [greater than or equal to] 38, [q.sub.2](n + 1) > [q.sub.2](n).

Proof: The inequality holds for n = 38, see Tab. 3. Otherwise, using formula (15) we get the following quotients all larger than 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to see this result, consider the case n mod 7 = r, r = 0,..., 6. Next on finding (n+1) mod 7, use formula (15).

The function [q.sub.2] is not monotone because of its small values precisely at n = 15, 22, 29. Moreover, [q.sub.2](n + 1) = [q.sub.2](n) precisely for n = 23, 30, 37. Nevertheless, the following important result holds.

Lemma 4 For n [greater than or equal to] 7 and n [not equal to] 8, [q.sub.2](n + 3) > [q.sub.2](n).

Proof: The result follows from Tab. 3 for n [less than or equal to] 37; otherwise from Theorem 3.

6 Main results

For maximum trees T with |T| [less than or equal to] 10, see Proposition 4.

Theorem 4 Maximum trees T with |T| [greater than or equal to] 7 and |T| [not equal to] 8 are [T.sup.2]-maximum.

Proof: Theorem is true for n = 7, 9, 10 by Proposition 4. Let T be a maximum tree of order n [greater than or equal to] 11. Then q(T) [greater than or equal to] [q.sub.2](n) [greater than or equal to] 5 by Tab. 3 and Lemma 4. Due to Corollary 2, for even n [greater than or equal to] 10 each n-vertex tree T with b(T) = 1 has q(T) [less than or equal to] n-4 / 2 < [q.sub.2](n) by Tab. 3 and Theorem 2. Therefore b(T) = 1 is possible only if n is odd and then by Corollary 2 maximum tree is [T.sup.2]-maximum.

We proceed by induction on n. Consider the case b(T) [greater than or equal to] 2. For any fixed x [member of] B(T), let [[tau].sub.i] = [[tau].sub.i](x), i = 0, 1, 2.

A. All twigs in T have length 1 or 2 (whence [[tau].sub.0] = 0). Due to Lemma 1, there is no x [member of] PB(T) with [[tau].sub.1] [greater than or equal to] 2 and [[tau].sub.2] [greater than or equal to] 1. Hence precisely two following subcases A1, A2 are possible.

A1. There exists an x [member of] PB(T) such that (i) [[tau].sub.1] [greater than or equal to] 2 and [[tau].sub.2] = 0 or (ii) [[tau].sub.1] = 1 and [[tau].sub.2] [greater than or equal to] 1. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then |T'| = |T|-2 [greater than or equal to] 9. We consider two subcases [[tau].sub.1] = 2, [[tau].sub.1] > 2 in case (i), two ones [[tau].sub.2] = 1, [[tau].sub.2] > 1 in case (ii), we use Lemma 1, and we see that q(T) [less than or equal to] q(T'). Let T" be a maximum tree of order |T'|. Then T" [member of] [T.sup.2]. Attaching a twig of length 2 to a PB-vertex of T" gives a tree T* of order |T| such that T* [member of] [T.sup.2] and, by (9), q(T*) > q(T") [greater than or equal to] q(T') [greater than or equal to] q(T), a contradiction.

A2. [[tau].sub.1] = 0 and [[tau].sub.2] [greater than or equal to] 2 for each x [member of] PB(T). Let n = 11. Consider an auxiliary 6-vertex graph H of the capital letter H. Then T = S(H), the subdivision of H, is the only possibility. However, q(T) = 1 < [q.sub.2](11) = 5, a contradiction, cf. Tab. 3. Let n [greater than or equal to] 12. Assume that x [member of] PB(T) and degree of x is as small as possible. Let T' = T'-*x. Then |T| - |T'| = 2[[tau].sub.2](x) + 1 which is odd and [greater than or equal to] 5. Hence, by the choice of x, |T'| [greater than or equal to] |T|/2| and |T'| [greater than or equal to] 7. Moreover, by Lemma 2, q(T) [less than or equal to] [[tau].sub.2] x q(T') where the equality holds whenever the attachment vertex a(x) is EDS-avoided in T' and T' is a maximum tree since so is T. Therefore if |T'| [not equal to] 8 then, by induction hypothesis, T' [member of] [T.sup.2] whence, by Proposition 7, T [member of] [T.sup.2] (as required). Otherwise |T'| = 8, each maximum T' has an EDS-avoided vertex and q(T') = 2, cf. Proposition 4. Consequently, q(T) = 2[[tau].sub.2](x). Hence, by Observation 2, q(T) = q(T") for some T" [member of] [T.sup.2] with b(T") = 2 and |T"| = |T| -3, a contradiction in view of Lemma 4.

B. T has a twig of length 3 or more. Assume that a tree T' is a 3-reduction of T whence |T'| = |T|-3 [greater than or equal to] 8. By Proposition 2, q(T') = q(T). Moreover, T' is clearly a maximum tree on |T| - 3 vertices. If |T'| = 8 then q(T') = 2 by Proposition 4. However, |T| = 11 and q(T) [greater than or equal to] 5 by Tab. 3 whence q(T) [not equal to] q(T'), a contradiction. Otherwise |T'| [greater than or equal to] 9 and T' [member of] [T.sup.2] by the induction hypothesis. Due to Lemma 4, [q.sub.2](|T'| + 3) > q(T'), a contradiction to q(T) = q(T').

Theorem 5 The number of maximum n-vertex trees is bounded below by the number |[T.sub.b]| of b-vertex trees where b = b(n) ~ n/7 as n [right arrow] [infinity]. The lower bound is exponential in n and is attained if 7/n and n [greater than or equal to] 35.

Proof: Let n be a natural number, n [greater than or equal to] 39 or n = 33, 35, 37. Then n = 7b + 2s with s = -1, 0, ..., 5 and b [greater than or equal to] 5 being uniquely defined in (12) and (13), respectively. Due to Theorem 4, any maximum n-vertex tree, T, is an element of [T.sup.2,max.sub.n]. The structural parameters [m.sub.k] of T, defined in formula (11), are determined in Proposition 8 and Theorem 2 in terms of s. Hence, due to very definition of the class [T.sup.2] in Sect. 4 and Observation 2, the tree T is obtained in the following way. Choose any tree T' on b vertices, select a subset S of |s| vertices in T'; for s [not equal to] 0, attach two or four twigs of length two to each vertex in S according as s = -1 or s > 0, and, finally, attach three such twigs to each of remaining vertices in T'. Then the resulting graph includes T' as an induced subgraph and has really 7b + 2s vertices as required. Define [r.sub.t](T') to be the number of distinct selections of t vertices in T', t [less than or equal to] b, two such selections being distinct if no automorphism of T' transforms one selection into another. Therefore

|T.sup.max.sub.n]| = [summation over (T' [member of] [T.sub.b])] [r.sub.|s|] (T') (16)

If n mod 7 = 0 and n [greater than or equal to] 35 then, by Theorem 2, b = n / 7 and T has exactly three twigs of length two at every B-vertex. Hence |[T.sup.max.sub.n]| = |[T.sub.b]|. In remaining cases, by formula (16), the number of maximum n-vertex trees is greater than |[T.sub.b]|. Therefore |[T.sup.max.sub.n] [greater than or equal to] |[T.sub.b]|. The lower bound is exponential in n since so is the cardinality of the class of b-vertex unlabeled trees [6, Sect. 9.5]. 2

Corollary 4 Formula (16) gives the number of maximum n-vertex trees for large enough n. 2

7 Concluding remarks

Let [T.sub.n] be an n-vertex tree with largest possible number of EDS'. Let n [greater than or equal to] 7 and n [not equal to] 8. Then [T.sub.n] [member of] [T.sup.2,max.sub.n] and [T.sub.n] has the following properties. Each leaf is on a twig of length 2. At least two and at most six twigs are attached to each branch vertex of [T.sub.n]. Numbers of twigs at different branch vertices differ by 0 or 1 only. Branch vertices induce a subtree, say [T".sub.n], [T".sub.n] = <B([T.sub.n])>, and the number, b, of branch vertices depends on n only, see Tab. 3 and formula (14) for values of b. Moreover, each tree [T'.sub.b] b of order b [greater than or equal to] 1 is [T".sub.n] for a certain [T.sub.n]. Let b [greater than or equal to] 5 and let n = 7b - 2; 7b,..., 7b + 10. Then there is a [T.sub.n] with [T".sub.n] [congruent to] [T'.sub.b] for each [T'.sub.b] and each of listed n only. Furthermore, if s := (n - 7b)/2 then s [member of] {-1, 0,..., 5} and if three twigs are attached to each of any n - |s| vertices of any [T'.sub.b], and 3 + sign(s) twigs (2 or 4) to each of remaining |s| vertices, then the resulting tree is a [T.sub.n]. Conversely, for each of listed n's and any [T.sub.n], [T".sub.n] is of order b.

Notice in this context the importance of Observation 2. It shows how to pass from an integer q to a variety of trees T such that q(T) = q (but to a single T only, if q is a prime).

We conclude this paper with a few open problems that we find interesting. Let [d.sub.G](x; y) stand for the distance between vertices x and y in G. Let p be a positive integer, p [greater than or equal to] 1. A vertex subset S*, S* [[subset].bar] V(G), is called an efficient p-dominating set of G if the following two properties are satisfied.

* for each x [not member of] S*, there exists y [member of] S* at distance at most p from x, [d.sub.G](x, y) [less than or equal to] p,

* the distance between any two vertices of S* is at least 2p + 1 (i.e. [d.sub.G](x; y) [greater than or equal to] 2p + 1), if x, y [member of] S* and x [not equal to] y.

Thus an efficient dominating set is efficient 1-dominating.

Open problems. For any integer p [greater than or equal to] 2, characterize trees

(1) which have an efficient p-dominating set,

(2) which have a fixed order and the largest number of efficient p-dominating sets.

Acknowledgements

The authors thank the referees for careful reading and stimulation which resulted in improving and simplifying the presentation of results.

received Nov. 16, 2006, revised Jan. 5, 2008, accepted Jan. 15, 2008.

References

[1] D.W. Bange, A.E. Barkauskas, P.J. Slater, Disjoint dominating sets in trees, Sandia Laboratories Report, SAND 78-1087J, 1978.

[2] D.W. Bange, A.E. Barkauskas, P.J. Slater, Efficient dominating sets in graphs, in: R.D. Ringeisen, F.S. Roberts, eds., Applications of Discrete Mathematics (Proc. 3rd Conf. on Discrete Math., Clemson, SC, 1986), SIAM Philadelphia, PA, 1988, pp. 189-199.

[3] A.E. Barkauskas, L.H. Host, Finding efficient dominating sets in oriented graphs, Congr. Numer. 98 (1993) 27-32.

[4] D. Brod, Z. Skupien, Trees with extremal numbers of dominating sets, Australas. J. Combin. 35 (2006) 273-290.

[5] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

[6] F. Harary, E.M. Palmer, Graphical Enumeration, Acad. Press, New York and London, 1973.

[7] T.W. Haynes, M.A. Henning, Ch. 9.2, Domination in graphs, in: J.L. Gross, J. Yellen, eds., Handbook of Graph Theory, CRC Press, Boca Raton et al., 2004, pp. 889-909.

[8] S.T. Hedetniemi, A.A. McRae, D.A. Parks, Complexity Results, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater, eds., Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York et al., 1998, pp. 233-269.

[9] J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3(1) (1965) 23-28.

[10] B.E. Sagan, A note on independent sets in trees, SIAM J. Discrete Math. 1 (1988) 105-108.

[11] A.J. Schwenk, B.Q. Yue, Efficient dominating sets in labeled rooted oriented trees, Discrete Math. 305 (2005) 276-298.

[12] Z. Skupien, On counting maximum path-factors of a tree, in: Algebra und Graphentheorie (Proc. Siebenlehn 1985 Conf.), Bergakademie Freiberg, Sektion Math. (1986) 91-94.

[13] Z. Skupien, From tree path-factors and doubly exponential sequences to a binomial inequality, in: R. Bondendiek and R. Henn, eds. Topics in Combinatorics and Graph Theory (Essays in Honour of Gerhard Ringel; Physica-Verlag, Heidelberg, 1990) 595-603.

[14] I. Tomescu, Le nombre maximum de cliques et de recouvrements par cliques des hypergraphes chromatiques complets, Discrete Math. 37 (1981) 263-271.

[15] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996.

[16] H.S. Wilf, The number of maximal independent sets in a tree, SIAM J. Alg. Discrete Math. 7 (1986) 125-130.

[17] J. Zito, The structure and maximum number of maximum independent sets in trees, J. Graph Theory 15(2) (1991) 207-221.

Dorota Brod (1) and Zdzislaw Skupien (2)

(1) Faculty of Mathematics and Applied Physics, Technical University of Rzeszow, W. Pola 2, 35-959 Rzeszow, Poland, e-mail: dorotab@prz.edu.pl

(2) Faculty of Applied Mathematics, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Krakow, Poland, e-mail: skupien@agh.edu.pl
Tab. 1:

n               7       9      10      11      12

[b.sub.2](n)    1       1       2       1       2
[q.sub.2](n)    3       4     2 x 2     5     2 x 3

n               13     14      16      18

[b.sub.2](n)    1       2       2       2
[q.sub.2](n)    6     3 x 3   3 x 4   4 x 4

Tab. 2: Inequalities L < R = [q.sub.2](n) for some
n [greater than or equal to 15

7 < [2.sup.3];                             (b = 3)    n = 15;
8 < [2.sup.2] x 3;                                    n = 17;
9 < 2 x [3.sup.2];                                    n = 19;
[2.sup.3] x [3.sup.2] < [4.sup.2] x 5;                n = 29;
4 x [5.sup.2] < [2.sup.2] x [3.sup.3];     (b = 5)    n = 31;
[5.sup.3] < 2 x [3.sup.4];                            n = 33;
[2.sup.2] x [3.sup.5] < [4.sup.5];                    n = 45;
[4.sup.4] x 5 < 2 x [3.sup.6];             (b = 7)    n = 47;

[2.sup.4] < 4 x 5;                                    n = 20;
[2.sup.3] x 3 < [5.sup.2];                            n = 22;
5 x 6 < [2.sup.2] x [3.sup.2];             (b = 4)    n = 24;
[6.sup.2] < 2 x [3.sup.3];                            n = 26;
[2.sup.3] x [3.sup.3] < [4.sup.4;]                    n = 36;
[4.sup.3] x 5 < [2.sup.2] x [3.sup.4];     (b = 6)    n = 38;
[2.sup.2] x [3.sup.6] < 3 x [4.sup.5];                n = 52;
[4.sup.6] < 2 x [3.sup.7];                 (b = 8)    n = 54:

Tab. 3:

n     b     [q.sub.2](n)

7     1     3
9     1     4
11    1     5
13    1     6
15    3     8 = [2.sup.3]
17    3     12 = [2.sup.2] x 3
19    3     18 = 2 x [3.sup.2]
21    3     27 = [3.sup.3]
23    3     36 = [3.sup.2] x 4
25    3     48 = 3 x [4.sup.2]
27    3     64 = [4.sup.3]
29    3     80 = [4.sup.2] x 5
31    5     108 = [2.sup.2] x [3.sup.3]
33    5     162 = 2 x [3.sup.4]
35    5     243 = [3.sup.5]
37    5     324 = [3.sup.4] x 4
39    5     432 = [3.sup.3] x [4.sup.2]

n     b     [q.sub.2](n)

10    2     4 = [2.sup.2]
12    2     6 = 2 x 3
14    2     9 = [3.sup.2]
16    2     12 = 3 x 4
18    2     16 = [4.sup.2]
20    2     20 = 4 x 5
22    2     25 = [5.sup.2]
24    4     36 = [2.sup.2] x [3.sup.2]
26    4     54 = 2 x [3.sup.3]
28    4     81 = [3.sup.4]
30    4     108 = [3.sup.3] x 4
32    4     144 = [3.sup.2] x [4.sup.2]
34    4     192 = 3 x [4.sup.3]
36    4     256 = [4.sup.4]
38    6     324 = [2.sup.2] x [3.sup.4]
40    6     486 = 2 x [3.sup.5]

Tab. 4:

s         -1   0   1   2   3   4   5
n mod 7    5   0   2   4   6   1   3
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Brod, Dorota; Skupien, Zdzislaw
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:4EXPO
Date:Jan 1, 2008
Words:6859
Previous Article:On quadratic residue codes and hyperelliptic curves.
Next Article:Sufficient conditions for labelled 0-1 laws.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters