ABSTRACT

A graph G is said to have a perfect dominating set S if S is a set of vertices of G and for each vertex v of G, either v is in S and v is adjacent to no other vertex in S, or v is not in S but is adjacent to precisely one vertex of S. A graph G may have none, one or more than one perfect dominating sets. The problem of determining if a graph has a perfect dominating set is NP-complete. The problem of calculating the probability of an arbitrary graph having a perfect dominating set seems also difficult. In 1994 Yue [1] conjectured that almost all graphs do not have a perfect dominating set. In this paper, by introducing multiple interrelated generating functions and using combinatorial computation techniques we calculated the number of perfect dominating sets among all trees (rooted and unrooted) of order n for each n up to 500. Then we calculated the average number of perfect dominating sets per tree (rooted and unrooted) of order n for each n up to 500. Our computational results show that this average number is approaching zero as n goes to infinity thus suggesting that Yue’s conjecture is true for trees (rooted and unrooted).

Keywords:

Tree, Dominating, Graph, Generating Function

1. Introduction

A vertex v in a graph G is said to dominate itself and its neighbors. A set S of vertices in a graph G is said to be a dominating set for G if every vertex of G is dominated by at least one member of S. A set S of vertices in a graph G is said to be a perfect dominating set for G if every vertex of G is dominated by exactly one member of S. If a graph G with vertex set V has a perfect dominating set of $S=\left\{u_1,u_2,\cdots ,u_k\right\}$ , then V can be partitioned into k subsets $N\left(u_i\right)$ , $\left(1\le i\le k\right)$ , where $N\left(u_i\right)$ is the set of vertex $u_i$ together with its neighbors, i.e. $V={\displaystyle \underset{i=1}{\overset{k}{\cup }}N\left(u_i\right)}$ . The concept of perfect domination set in a graph has wide range of applications. For example, resource allocation and placement in parallel computers [2] , code error detecting and correcting [3] . In social networking context, if G is the graph presentation of a social network and if G has a perfect dominating set S, then the members of S are independent influencers that will completely influence the entire network, and each non-influencing member of G will be influenced by exactly one influencer from S. For such a social network G, if we can identify one perfect dominating set S, we can focus on S instead of entire social network when we want to influence, do campaign for instance, on the entire network. In the context of a common UNIX file system in which we consider only directories, a rooted tree T can be used to completely represent the entire file system. If we can configure T so that T has a perfect dominating set S, then each node in S can be assigned an agent, these agents are independent and can carry out monitoring or security checks on entire system in very efficient manner.

A graph can have none, one or more than one perfect dominating sets. See Figure 1. In Figure 1, graph $G_1$ has no perfect dominating set, $G_2$ has one perfect dominating set {1, 4, 7} and $G_3$ has two perfect dominating sets {1, 4, 7} and {2, 8, 6}.

For a graph G, three questions can be asked: “Does G have a perfect dominating set?” “If G has perfect dominating set(s), how many are there, what are they?” “What is the probability of one arbitrary graph G having a perfect dominating set?” The problem of determining if a graph has a perfect dominating set is NP-complete [4] [5] , and the problem remains NP-complete even if the graphs are restricted to 3-regular planar graphs. Thus the problem of determining if a graph has a perfect dominating set is quite difficult. The second question also seems very difficult. For the third question, in 1994 Yue [1] conjectured that almost all graphs do not have a perfect domination set.

For a given tree, Livingston and Stout have obtained linear algorithms to answer the first question and the second question [6] . In this paper, we will focus on and study trees (rooted and unrooted) by using combinatorial computational techniques to answer a part of the second question (how many perfect dominating sets) and the third question from completely different standpoint.

From onwards unless otherwise stated, the trees considered are rooted and unrooted.

We first compute the number of perfect dominating sets among all trees of

order n for each n up to 500 then we calculate the average number of perfect dominating sets per tree of order less than or equal to n for each n up to 500. Since a tree can have at most finite number of perfect dominating sets, if this average number is approaching zero as n gets bigger then we can say that it provides computation evidence of Yue’s conjecture being true for trees.

Unlike other graph counting problems, it appears impossible to obtain recursive formulas for the number of perfect dominating sets among all trees directly. So, instead of using a single generating function, we introduce four interrelated generating functions and obtain recursive formula for each, then we use these formulas to find the number of perfect dominating sets among all trees of order n for each n up to 500. We then calculate the number of trees of order n for each n up to 500 and finally calculate the average number of perfect dominating sets per tree of order less than or equal to n for each n up to 500.

The notation and terminology in this paper follow that in Harary and Palmer [7] and Chartrand [8] . In particular, $Z\left(S_n\right)=Z\left(S_n\mathrm{<mo>\; ;\; </mo>}{s}_1\mathrm{,}{s}_2\mathrm{,}\cdots \mathrm{,}{s}_n\right)$ is the cycle index for the symmetric group $S_n$ acting on n objects. This is a polynomial in n variables $s_1\mathrm{,}{s}_2\mathrm{,}\cdots \mathrm{,}{s}_n$ . For any generating function $g\left(x\right)$ , $Z\left(S_n\mathrm{<mo>\; ;\; </mo>}g\left(x\right)\right)$ is a shorthand representing the substitution $s_1=g\left(x\right),s_2=g\left(x^2\right),\cdots$ in $Z\left(S_n\right)$ .

For related results see [2] and [3] , for terminologies readers are referred to [7] [8] and [9] .

2. Generating Functions for Rooted Trees

In order to compute the number of perfect dominating sets among all rooted trees we would like introduce four generating functions. We let

$P\left(x\right)={\displaystyle \sum _{n=1}^{\infty }}{P}_n{x}^n$

be the generating function in which $P_n$ is the number of perfect dominating sets among all rooted trees of order n. Unlike other graph counting problems, it is not possible to obtain recursive formulas for the number of perfect dominating sets among all trees directly, so we introduce other three interrelated generating functions.

Let

$R\left(x\right)={\displaystyle \sum _{n=1}^{\infty }}{R}_n{x}^n$ (1)

be the generating function in which $R_n$ is the number of perfect dominating sets among all rooted trees of order n which have the root in the dominating set. (The root is dominated by itself.) We call these rooted trees as perfectly dominated rooted trees of type I.

Let

$C\left(x\right)={\displaystyle \sum _{n=1}^{\infty }}{C}_n{x}^n$ (2)

be the generating function in which $C_n$ is the number of perfect dominating sets among all rooted trees of order n which have the root dominated by one of its children. (The root is dominated from inside.) We call these rooted trees as perfectly dominated rooted trees of type II.

We let the forth series be

$B\left(x\right)={\displaystyle \sum _{n=1}^{\infty }}{B}_n{x}^n$ (3)

In this series $B\left(x\right)$ , we would like to count sets that are nearly perfect dominating sets among all rooted trees of order n. For each such a rooted tree T, we should like to count the sets with the property that for each such a set S, with the exception of the root, every vertex is perfectly dominated by a unique vertex in the set S. But the root is neither in S nor is it dominated by any vertex in S. Such a tree T is not perfectly dominated, but it can be a branch in a larger perfectly dominated tree of type I. (The root is dominated from outside.) We call these branches as branches of type B.

Observe that the number of perfect dominating sets among all rooted trees of order n equals the sum of perfectly dominated rooted trees of type I of order n and perfectly dominated rooted trees of type II of order n, i.e. $P_n=R_n+C_n$ , since for any perfect dominating set S, the root must either be in S or be dominated by one of its children.

Thus we have

$P\left(x\right)=R\left(x\right)+C\left(x\right).$ (4)

It may seem that $B\left(x\right)$ is not involved in the process of counting the number of perfect dominating sets, but we shall soon see we need it to calculate $R\left(x\right)$ and $C\left(x\right)$ .

3. Functional Relations among the Counting Series

Our object is to find the number of perfect dominating sets among all rooted trees of order n. In the previous section we saw that this number is equal to $R_n+C_n$ . We first find the functional relations among $R\left(x\right),C\left(x\right)$ and $B\left(x\right)$ then generate $R_n$ and $C_n$ for every n up to 500.

Theorem 1. For the functions introduced in (1), (2) and (3) the following equations hold:

$R\left(x\right)=x\left[{\displaystyle \sum _{k=0}^{\infty }}Z\left(S_k,B\left(x\right)\right)\right]$ (5)

$C\left(x\right)=R\left(x\right)B\left(x\right)$ (6)

$B\left(x\right)=x\left[{\displaystyle \sum _{k=0}^{\infty }}Z\left(S_k,C\left(x\right)\right)\right]$ (7)

Proof: First observe that for any rooted tree T, if T has a perfect dominating set, every branch of T must be one of perfectly dominated trees of type I, or perfectly dominated trees of type II or one branch of type B. Also observe that any rooted tree that is perfectly dominated tree of type I, perfectly dominated tree of type II or branch of type B must have the property that it is built by a root and some (maybe none) branches of perfectly dominated tree of type I, or some (maybe none) perfectly dominated tree of type II or some (maybe none) branch type B.

Now we would like to examine the structure of rooted trees of perfectly dominated tree of type I, perfectly dominated tree of type II and branch of type B respectively.

For perfectly dominated tree of type I, any branch of perfectly dominated tree of type I is invalid since otherwise both root of the tree and root of the branch will be in the dominating set, contradicting the property of perfectly dominating set. Any branch of perfectly dominated tree of type II is invalid since otherwise the root of the branch will be dominated twice, contradicting the property of perfectly dominating set. On the other hand, it can have any number of branches of type B. See Figure 2.

This allows us to deduce the Equation (5):

$R\left(x\right)=x\left[{\displaystyle \sum _{k=0}^{\infty }}Z\left(S_k,B\left(x\right)\right)\right].$

In this expression, the factor x accounts for the root. Each $Z\left(S_k,B\left(x\right)\right)$ allows for k branches of type B. Thus the structure shown in Figure 2 leads us to Equation (5).

For rooted trees of perfectly dominated tree of type II, it must have exactly one branch of perfectly dominated tree of type I and the rest of it must be a branch of type B. See Figure 3.

That gives us the Equation (6):

$C\left(x\right)=R\left(x\right)B(x)$

For a branch type B, any branch of perfectly dominated tree of type I is invalid since otherwise the root of the tree will be dominated, contradicting the property of branch of type B. It can have any number of branches of type type II. It cannot have any branch of type B since otherwise the root of the branch would not be dominated, contradicting the property of rooted tree of type B. See Figure 4.

So we have the Equation (7):

$B\left(x\right)=x\left[{\displaystyle \sum _{k=0}^{\infty }}Z\left(S_k,C\left(x\right)\right)\right].$

4. Recurrence Relations and Numerical Values for Rooted Trees

Although the following two equations can be derived from (5) and (7) (see [7] ), we would like to use combinatorial arguments to obtain them.

$R\left(x\right)=x{\displaystyle \prod _{k=1}^{\infty }}{\left(1+x^k+x^{2k}+\cdots \right)}^{B_k}$ (8)

$B\left(x\right)=x{\displaystyle \prod _{k=1}^{\infty }}{\left(1+x^k+x^{2k}+\cdots \right)}^{C_k}$ (9)

See Figure 2 again, we examine the following expression:

$x{\displaystyle \prod _{k\mathrm{<mo>\; =\; </mo>\; 1}}^{\infty }}{\left(1+x^k+x^{2k}+\cdots \right)}^{B_k}\mathrm{.}$

In this expression, x counts the root. The number 1 represents no branch of order k; the term $x^k$ represents one branch of order k, $x^{2k}$ represents two branches of order k, and so on. The number $B_k$ represents the number of ways to select a branch of type B of order k.

Then observe that the product of all these is, by the structure of perfectly dominated tree of type I, $R\left(x\right)$ . That is Equation (8). By similar arguments, we can get (9).

Knowing that $R_1=1$ , $B_1=1$ , $C_1=0$ , theoretically these recurrence relations allow us to compute $R_n$ , $B_n$ , $C_n$ for any particular n. For example if we want to calculate $R_m$ , $B_m$ , $C_m$ , we only need to know $R_n$ , $B_n$ , $C_n$ for each n up to $m-1$ .

By using (8), (9) and (6) on on a 64bit-based PC with a CPU process of T4200 (Pentium(R) Dual-Core) and RAM of 4 GB we can determine $R_n$ , $B_n$ , $C_n$ for each n up to 10 in 0.165 seconds, for each n up to 15 in 29.2 seconds and for each n up to 20 in 5719.8 seconds. At n equals 25, the same PC failed to manage the complexity of calculations. In order to determine $R_n$ , $B_n$ , $C_n$ for each n up to 500 more efficiently we need to modify (8), (9) and (6).

In Equation (8) we rewrite the geometric series and then use the binomial theorem with negative exponents to get

$\begin{array}{c}R\left(x\right)=x{\displaystyle \prod _{k=1}^{\infty }}{\left(1+x^k+x^{2k}+\cdots \right)}^{B_k}\\ =x{\displaystyle \prod _{k=1}^{\infty }}{\left(1-x^k\right)}^{-B_k}\\ =x{\displaystyle \prod _{k=1}^{\infty }}{\displaystyle \sum _{l=0}^{\infty }}\left(\begin{array}{c}{B}_k+l-1\\ l\end{array}\right)x^{kl}.\end{array}$

Similarly, from (9) we have

$B\left(x\right)=x{\displaystyle \prod _{k=1}^{\infty }}{\displaystyle \sum _{l=0}^{\infty }}\left(\begin{array}{c}{C}_k+l-1\\ l\end{array}\right)x^{kl}.$

Formally expanding the product of two series in (6) gives

$C\left(x\right)={\displaystyle \sum _{k=2}^{\infty }}\left({\displaystyle \sum _{l=1}^{k-1}}{R}_l{B}_{k-l}\right)x^k.$

To find out the formulas to calculate $R_n$ , $B_n$ , $C_n$ for each n up to 500, we first introduce some notation. Let $f\left(x\right)={\displaystyle \sum _{n=0}^{\infty }}{f}_n{x}^n$ be any power series, then $\left[x^n\right]f\left(x\right)=f_n$ . For example $\left[x^n\right]{\text{e}}^{-x}=\frac{{\left(-1\right)}^n}{n!}$ .

Now suppose we would like to find $R_m\mathrm{,}{B}_m$ and $C_m$ $\left(2\le m\le 500\right)$ , then

$R_m=\left[x^m\right]\left[x{\displaystyle \prod _{k=1}^{m-1}}{\displaystyle \sum _{l=0}^{\lfloor \frac{m-1}{k}\rfloor }}\left(\begin{array}{c}{B}_k+l-1\\ l\end{array}\right)x^{kl}\right]$

$B_m=\left[x^m\right]\left[x{\displaystyle \prod _{k=1}^{m-1}}{\displaystyle \sum _{l=0}^{\lfloor \frac{m-1}{k}\rfloor }}\left(\begin{array}{c}{C}_k+l-1\\ l\end{array}\right)x^{kl}\right]$

$C_m={\displaystyle \sum _{k=1}^{m-1}}{R}_k{B}_{m-k}.$

With the aid of the same computer and Mathematica, these three formulas provide $R_n$ , $B_n$ ,and $C_n$ for each n up to 500.

5. Equation and Numerical Values for Unrooted Trees

Now we are in the position to determine the number of perfect dominating sets among all unrooted trees of order p.

We have seen that (4):

$P\left(x\right)=R\left(x\right)+C(x)$

is the generating function in which $P_n$ is the number of perfect dominating sets among all rooted trees of order n.

We let

$p\left(x\right)={\displaystyle \sum _{n=1}^{\infty }}{p}_n{x}^n$

be the generating function in which $p_n$ is the number of perfect dominating sets among all unrooted trees of order n.

Theorem 2. The counting series $p\left(x\right)$ satisfies

$p\left(x\right)=R\left(x\right)-\frac{1}{2}\left[C^2\left(x\right)-C\left(x^2\right)\right].$ (10)

Proof: We will use the following Theorem (Dissimilarity characteristic theorem for trees) due to Otter [10] and presented in [7] .

For any tree T of order n

$1=n^{*}-q^{*}+s.$ (11)

In the equation $n^{\mathrm{<mo>\; *\; </mo>}}$ is the number of dissimilar vertices of T, or more precisely, the number of equivalence classes of vertices of T under action of the symmetric group of $S_n$ ; $q^{\mathrm{<mo>\; *\; </mo>}}$ is the number of dissimilar edges of T, or more precisely, the number of equivalence classes of edges of T under action of the symmetric group of $S_n$ ; s is the number of symmetric edges of T under action of the symmetric group of $S_n$ .

To illustrate the Theorem 2, we look the ordinary tree $T_1$ and the ordinary tree $T_2$ both of order 6 in Figure 5.

For tree $T_1$ , $n^{*}=4$ , $q^{*}=3$ and $s=0$ , so $1=n^{*}-q^{*}+s$ . For tree $T_2$ , $n^{*}=2$ , $q^{*}=2$ and $s=1$ , hence $1=n^{*}-q^{*}+s$ .

Observe that each unrooted tree T can give rise to exactly $n^{\mathrm{<mo>\; *\; </mo>}}$ different rooted trees and each unrooted tree T can be “rooted” at an edge in $q^{\mathrm{<mo>\; *\; </mo>}}$ different ways. Also observe that for any unrooted tree T, two end vertices of a symmetric edge (if there is any) must be in the center of T. So s equals 0 or 1.

Now we apply Theorem 2 to our tree problem. Sum (11) over all unrooted

trees that have a perfect dominating set and that have exactly n vertices. The result is

${\displaystyle \sum }1={\displaystyle \sum }{n}^{*}-{\displaystyle \sum }{q}^{*}+{\displaystyle \sum }s$

but ${\displaystyle \sum }1=p_n$ and ${\displaystyle \sum }{n}^{*}=P_n$ . Furthermore, ${\displaystyle \sum }{q}^{*}$ is the number of perfect dominating sets among all trees that are rooted at an edge and have the order of n. There are six possible ways to attach two branches to an rooted edge, i.e. $\left\{R,R\right\},\left\{R,B\right\},\left\{R,C\right\},\left\{B,B\right\},\left\{B,C\right\}$ and $\left\{C\mathrm{,}C\right\}$ but only two ways are valid. First, if one branch is type R then another branch must be type B. Secondly, if one branch is type C then another branch must be type also C. See Figure 6.

Hence we have

${\displaystyle \sum }{q}^{*}=R\left(x\right)B\left(x\right)+Z\left(S_2,C\left(x\right)\right).$

Observe that for a tree that is rooted at an edge and s equals 1, then the two branches attached to the rooted edge must be exactly same two branches of type C, so

${\displaystyle \sum }s=C\left(x^2\right).$

Finally, we have

$p\left(x\right)=P\left(x\right)-\left[R\left(x\right)B\left(x\right)+Z\left(S_2,C\left(x\right)\right)\right]+C\left(x^2\right),$

or

$p\left(x\right)=P\left(x\right)-R\left(x\right)B\left(x\right)-\frac{1}{2}\left[C^2\left(x\right)+C\left(x^2\right)\right]+C\left(x^2\right).$

Recalling that $P\left(x\right)=R\left(x\right)+C\left(x\right)$ and $C\left(x\right)=R\left(x\right)B\left(x\right)$ , we get (10):

$p\left(x\right)=R\left(x\right)-\frac{1}{2}\left[C^2\left(x\right)-C\left(x^2\right)\right].$

We have $R_n$ and $C_n$ for every n up to 500 in hand, using (10) we can determine $p_n$ for each n up to 500.

6. Enumeration Results

Enumeration results of $R_n\mathrm{,}{B}_n\mathrm{,}{C}_n\mathrm{,}{P}_n$ and $p_n$ for each n up to 20 are presented in Table 1.

Using similar techniques we calculated the number rooted trees $T_n$ of order n for each n up to 500 and the number of unrooted trees $t_n$ of order n for each n up to 500. Then we calculated the average number of perfect dominating sets per rooted tree $\overline{P_n}=P_n/T_n$ of order n for each n up to 500 and the average number of perfect dominating sets per unrooted tree $\overline{p_n}=p_n/t_n$ of order n for each n up to 500.

Let $P{P}_n={\displaystyle {\sum }_{k=1}^{k=n}}{P}_k$ , $T{T}_n={\displaystyle {\sum }_{k=1}^{k=n}}{T}_k$ , $p{p}_n={\displaystyle {\sum }_{k=1}^{k=n}}{p}_k$ , $t{t}_n={\displaystyle {\sum }_{k=1}^{k=n}}{t}_k$ be the total number of perfect dominating sets among all rooted trees of order less than or equal to n, the total number rooted trees of order less than or equal to n, the total number of perfect dominating sets among all unrooted trees of order less than or equal to n and the total number unrooted trees of order less than or equal to n respectively, if $P{P}_n/T{T}_n$ is approaching zero as n getting larger then we may assert that it is the computational evidence of Yue’s conjecture being true for rooted trees. For the same reason, if $p{p}_n/t{t}_n$ is approaching zero as n getting larger then we may assert that it is the computational evidence of Yue’s conjecture being true for unrooted trees.

We can prove that (see [9] [11] ) $P{P}_n/T{T}_n$ is approaching zero as n getting larger whenever $\overline{P_n}$ is approaching zero as n getting larger and that $p{p}_n/t{t}_n$ is approaching zero as n getting larger whenever $\overline{p_n}$ is approaching zero as n getting larger. Hence if $\overline{P_n}$ is approaching zero as n getting larger then we can claim that it is the computational evidence of Yue’s conjecture being true for rooted trees and if $\overline{p_n}$ is approaching zero as n getting larger then we can claim that it is the computational evidence of Yue’s conjecture being true for unrooted trees. During the conversation with Paul Erdös, Erdös suggested to look at the nth roots of $\sqrt[n]{\overline{P_n}}$ and $\sqrt[n]{\overline{p_n}}$ since these two values can tell us the “rate” of $\overline{P_n}$ and $\overline{p_n}$ approaching zero.

Results of $\overline{P_n}$ , $\overline{p_n}$ , $\sqrt[n]{\overline{P_n}}$ and $\sqrt[n]{\overline{p_n}}$ for each various n are presented in Table 2.

7. Some Observations and Open Problems

From Table 2 we see $\sqrt[n]{\overline{P_n}}$ and $\sqrt[n]{\overline{p_n}}$ are approaching to about same value of 0.88 ... as n getting larger. Can we prove that they are actually convergent to the same limit? Can we find the limit?

We know for a perfect dominating set of rooted tree, the root is either dominated by itself or by one of its children, hence the number of perfect dominating sets among all rooted trees of order n is $P_n=R_n+C_n$ (4). We may ask what is the contribution of $R_n$ (or $C_n$ ) to $P_n$ ? The ratio of $R_n/P_n$ measures the contribution of $R_n$ to $P_n$ .

We have seen the average number of perfect dominating sets per rooted tree $\overline{P_n}$ is somewhat bigger than the average number of perfect dominating sets per unrooted tree $\overline{p_n}$ . Another interesting question to ask is on what percentage

does one rooted tree can give rise to more perfect dominating sets than that of one unrooted tree? The ratio of $\overline{P_n}/\overline{p_n}$ measures the difference.

Results of $R_n/P_n$ , $\overline{P_n}/\overline{p_n}$ for each various n are presented in Table 3. From Table 3 we see about 37% of perfect dominating sets for rooted trees in which the root is dominated by itself. On average per tree, rooted trees can give rise to about 7% more perfect dominating sets than unrooted trees.

In this paper, by introducing multiple interrelated generating function and using combinatorial computation techniques, we are able to compute the number of perfect dominating sets among all trees of order n for each n up to 500. As we observed earlier, a tree may have no perfect dominating set. We can define perfectly dominated tree to be a tree that has at least one perfect dominating set. Thus we can ask a question: “Can we develop an enumeration method to find the number of perfectly dominated trees of order n?” We also observed earlier, a tree may have more than one perfect dominating set. We can define maximal tree of order n to be a tree with largest possible number perfect dominating sets among all trees of order n. Then we can ask other questions: “Can we develop an algorithm to search maximal trees?” “What are characteristics a maximal trees?”

Cite this paper

Yue, B.Q. (2018) Do Almost All Trees Have No Perfect Dominating Set? Open Journal of Discrete Mathematics, 8, 1-13. https://doi.org/10.4236/ojdm.2018.81001

References