On the Uphill Domination Polynomial of Graphs

Thekra Alsalomy, Anwar Saleh, Najat Muthana, Wafa Al Shammakh

Department of Mathematics, Faculty of Science, University of Jeddah, Jeddah, Saudi Arabia.

DOI: 10.4236/jamp.2020.86088                

Abstract

A path π = [v₁, v₂, …, v_k] in a graph G = (V, E) is an uphill path if deg(v_i) ≤ deg(v_i+1) for every 1 ≤ i ≤ k. A subset S ⊆ V(G) is an uphill dominating set if every vertex v_i ∈ V(G) lies on an uphill path originating from some vertex in S. The uphill domination number of G is denoted by γ_up(G) and is the minimum cardinality of the uphill dominating set of G. In this paper, we introduce the uphill domination polynomial of a graph G. The uphill domination polynomial of a graph G of n vertices is the polynomial , where up(G, i) is the number of uphill dominating sets of size i in G, and γ_up(G) is the uphill domination number of G, we compute the uphill domination polynomial and its roots for some families of standard graphs. Also, UP(G, x) for some graph operations is obtained.

Keywords

Domination, Uphill Domination, Uphill Domination Polynomial

1. Introduction

In this paper, we are concerned with simple graphs which are finite, undirected with no loops nor multiple edges. Throughout this paper, we let $\left|V\left(G\right)\right|=n$ and $\left|E\left(G\right)\right|=m$. In a graph $G=\left(V\mathrm{,}E\right)$, the degree of $v\in V\left(G\right)$ denoted by $deg\left(v\right)$ is the number of edges that incident with v. A path in G is an alternating sequence of distinct vertices. A path is an uphill path if for every $1\le i\le k$ we have $deg\left(v_i\right)\le deg\left(v_{i+1}\right)$ [1].

The bistar graph $S_{k_1\mathrm{,}{k}_1}$ with $n=2k_1+2$ vertices is obtained by joining the non-pendant vertices of two copies of star graph $S_{k_1}$ by new edge. The corona of two graphs $G_1$ and $G_2$ with $n_1$ and $n_2$ vertices, respectively, denoted by $G=G_1\circ G_2$ is obtained by taking one copy of $G_1$ and $n_1$ copies of $G_2$ and joining the ith vertex of $G_1$ with an edge to every vertex in the ith copy of $G_2$. The corona $G\circ K_1$ (in particular) is the graph constructed by a copy of G, where for each vertex $v\in V\left(G\right)$ a new vertex $v^{\prime }$ and a pendant edge $v{v}^{\prime }$ are added. The tadpole graph $T_{s\mathrm{,}k}$ is a graph consisting of a cycle graph $C_s$ on at least three vertices and a path graph $P_k$ on k vertices connected with bridge. The wheel graph $W_s$ is a graph formed by connecting a single vertex to all vertices of a cycle graph $C_s$. The book graph is a Cartesian product $B_m=S_m\times P_2$, where $S_m$ is the star graph with $m+1$ vertices and $P_2$ is the path graph on two vertices. Also, the windmill graph $Wd\left(s\mathrm{,}k\right)$ is a graph constructed for $s\ge 2$ and $k\ge 2$ by joining k copies of the complete graph $K_s$ at a shared universal vertex. The dutch windmill graph $D\left(s\mathrm{,}k\right)$ is the graph obtained by taking k copies of the cycle graph $C_s$ with a vertex in common. Also, the friendship $F_k$ is a graph that constructed by joining k copies of the cycle graph $C_3$ and observes that $F_k$ is a special case of $D\left(s\mathrm{,}k\right)$. Finlay, the firefly graph $F_{s\mathrm{,}t\mathrm{,}k}$ with $s\mathrm{,}t\mathrm{,}k\ge 0$ and $n=2s+2t+k+1$ vertices is defined by consisting of s triangles, t pendent paths of length 2 and k pendent edges, sharing a common vertex. Any terminology not mentioed here we refer the reader to [2].

A set $S\subseteq V$ of vertices in a graph G is called a dominating set if every vertex $v\in V$ is either $v\in S$ or v is adjacent to an element of S, The uphill dominating set “UDS” is a set $S\subseteq V$ having the property that every vertex $v\in V$ lies on an uphill path originating from some vertex in S. The uphill domination number of a graph G is denoted by ${\gamma }_{up}\left(G\right)$ and is defined to be the minimum cardinality of the UDS of G. Moreover, it’s customary to denote the UDS having the minimum cardinality by ${\gamma }_{up}\left(G\right)$ -set, for more details in domination see [3] and [4].

Representing a graph by using a polynomial is one of the algebraic representations of a graph to study some of algebraic properties and graph’s structure. In general graph polynomials are a well-developed area which is very useful for analyzing properties of the graphs.

The domination polynomial [5] and the uphill domination of a graph [6], motivated us to introduce and study the uphill domination polynomial and the uphill domination roots of a graph.

2. Uphill Domination Polynomial

Definition 2.1. For any graph G of n vertices, the uphill domination polynomial of G is defined by

$UP(G,x)={\displaystyle \underset{i={\gamma }_{up}\left(G\right)}{\overset{n}{\sum }}}up\left(G,i\right)x^i,$

where $up\left(G,i\right)$ is the number of uphill dominating sets of size i in G. The set of roots of $UP\left(G\mathrm{,}x\right)$ is called uphill domination roots of graph G and denoted by $Z_{up}\left(G\right)$.

Example 2.2. The uphill domination polynomial of House graph H (as shown in Figure 1) with 6 vertices and ${\gamma }_{up}\left(H\right)=2$ is given by $UP\left(H\mathrm{,}x\right)=2x^2+7x^3+9x^4+5x^5+x^6$. Furthermore, $Z_{up}\left(H\right)=\left\{\mathrm{0,}-\mathrm{1,}-2\right\}$.

The following theorem gives the sufficient condition for the uphill domination polynomial of r-regular graph.

Theorem 2.3. Let G be connected graph with $n\ge 2$ vertices. Then, $UP\left(G\mathrm{,}x\right)={\left(1+x\right)}^n-1$ if and only if G is r-regular graph.

Proof. Let G be a connected graph of $n\ge 2$ vertices. Suppose that the uphill domination polynomial of G is given by

$UP\left(G,x\right)={\left(1+x\right)}^n-1=nx+\left(\begin{array}{c}n\\ 2\end{array}\right)x^2+\cdots +x^n$.

Since the first coefficient of the polynomial is n, then it is easily verified that for every $v\in V\left(G\right)$, the singleton vertex set $\left\{v\right\}$ is an UDS in G. Assume that G is not r-regular graph. Hence there exists a vertex $u\in V\left(G\right)$ such that $deg\left(u\right)=s\ne r$. Now, we have two cases:

Case 1: If $s>r$, then the set $\left\{u\right\}$ is not UDS which contradict that every singleton vertex set is an UDS in G.

Case 2: If $s<r$, then for all $u\ne v$ with $deg\left(v\right)=r$, we get the set $\left\{v\right\}$ is not UDS which is also contradict that every singleton vertex set is an UDS in G.

Thus, G must be r-regular graph.

On the other hand, suppose that G is r-regular graph with $n\ge 2$ vertices. We have ${\gamma }_{up}\left(G\right)=1$, then there exist n UDS of size one, while for $i=2$ there are $\left(\begin{array}{c}n\\ 2\end{array}\right)$ UDS and so on. Thus, we can write the uphill domination polynomial as

$UP\left(G,x\right)=nx+\left(\begin{array}{c}n\\ 2\end{array}\right)x^2+\left(\begin{array}{c}n\\ 2\end{array}\right)x^3+\cdots +\left(\begin{array}{c}n\\ n\end{array}\right)x^n={\left(1+x\right)}^n-1$.

Corollary 2.4. Let G ba a graph with s vertices. If G is a cycle $C_s$ or complete graph $K_s$, then $UP\left(G\mathrm{,}x\right)={\left(1+x\right)}^s-1$.

Corollary 2.5. The uphill domination polynomial for the regular graph $G=C_s\times C_k$ with sk vertices is given by $UP\left(G\mathrm{,}x\right)={\left(1+x\right)}^{sk}-1$.

Corollary 2.6. [6] Let G be a graph with m components. Then,

${\gamma }_{up}\left(G\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}}{\gamma }_{up}\left(G_i\right).$

Proposition 2.7. If a graph G with n vertices consists of m components $G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_m$, then

Figure 1. The House graph.

$UP\left(G,x\right)={\displaystyle \underset{i=1}{\overset{m}{\prod }}}UP\left(G_i,x\right).$

Proof. By using mathematical induction we found that for $m=1$ the statement is true and the proof is trivial. Suppose that the statement is true when $m=k$ such that

$UP\left(G,x\right)={\displaystyle \underset{i=1}{\overset{k}{\prod }}}UP\left(G_i,x\right).$

Now, we prove that the statement is true when $m=k+1$. Let G consists of $k+1$ components that mean $G=G_1\cup G_2\cup \cdots \cup G_{k+1}$. If the set $\left\{r_1\mathrm{,}{r}_2\mathrm{,}\cdots \mathrm{,}{r}_{k+1}\right\}$ represent the uphill domination number for the components of G respectively, such that ${\gamma }_{up}\left(G_i\right)=r_i$ $\forall 1\le i\le k+1$. Then, by Corollary (2.6) it easily to see that

${\gamma }_{up}\left(G\right)={\gamma }_{up}\left({\displaystyle \underset{1\le i\le k+1}{\cup }}{G}_i\right)={\displaystyle \underset{1\le i\le k+1}{\sum }}{\gamma }_{up}\left(G_i\right)=r_1+\cdots +r_{k+1}=r.$

Thus, $up\left(G\mathrm{,}r\right)$ is exactly equal the number of way for choosing an UDS of size $r_1$ in $G_1$ and an UDS of size $r_2$ in $G_2$ and so on. Hence, $up\left(G\mathrm{,}r\right)$ is the coefficient of $x^r$ in $UP\left(G_1,x\right)UP\left(G_2,x\right)\cdots UP\left(G_{k+1},x\right)$ and in $UP\left(G\mathrm{,}x\right)$. In the same argument we can proof for all $up\left(G\mathrm{,}j\right)$, where $r\le j\le n$ that

$up\left(G,j\right)=up\left(G_1,j\right)\cdots up\left(G_{k+1},j\right)={\displaystyle \underset{i=1}{\overset{k+1}{\prod }}}up\left(G_i,j\right).$

Thus, for $m=k+1$ the statement is true and the proof is done.

Theorem 2.8. For any path $P_n$ with $n\ge 3$ vertices, $UP\left(G\mathrm{,}x\right)=x^2{\left(1+x\right)}^{n-2}$. Furthermore, $Z_{up}\left(P_n\right)=\left\{\mathrm{0,}-1\right\}$.

Proof. Let G be a path graph $P_n$ with $n\ge 3$. We know that ${\gamma }_{up}\left(P_n\right)=2$, then there is only one UDS of size two. For $i=3$ there are $n-2$ UDS of size three and so on. Thus, we get

$\begin{array}{c}UP\left(G,x\right)=x^2+\left(\begin{array}{c}n-2\\ 1\end{array}\right)x^3+\left(\begin{array}{c}n-2\\ 2\end{array}\right)x^4+\cdots +\left(\begin{array}{c}n-2\\ n-2\end{array}\right)x^n\\ =x^2\left[1+{\displaystyle \underset{i=1}{\overset{n-2}{\sum }}}\left(\begin{array}{c}n-2\\ i\end{array}\right)x^i\right]\\ =x^2\left[{\displaystyle \underset{i=0}{\overset{n-2}{\sum }}}\left(\begin{array}{c}n-2\\ i\end{array}\right)x^i\right]\\ =x^2{\left(1+x\right)}^{n-2}.\end{array}$

Theorem 2.9. For any graph G. $UP\left(G\mathrm{,}x\right)=x^n$ if and only if $G\cong {\bar{K}}_n$.

Proof. Let G be a graph with $UP\left(G\mathrm{,}x\right)=x^n$. Since, $UP\left({\bar{K}}_1\mathrm{,}x\right)=x$, then we can write that

$\begin{array}{c}UP\left(G\mathrm{,}x\right)=x^n\\ =\underset{n\text{times}}{\underset{︸}{x\cdot x\cdots x}}\\ =\underset{n\text{times}}{\underset{︸}{UP\left({\bar{K}}_1\mathrm{,}x\right)\cdot UP\left({\bar{K}}_1\mathrm{,}x\right)\cdots UP\left({\bar{K}}_1\mathrm{,}x\right)}}\\ =UP\left({\bar{K}}_n\mathrm{,}x\right)\mathrm{.}\end{array}$

Thus, $G\cong {\bar{K}}_n$. On the other hand if $G\cong {\bar{K}}_n$, then by Proposition (2.7) we get $UP\left(G\mathrm{,}x\right)=x^n$.

Corollary 2.10. A graph G has one uphill domination root if and only if $G\cong {\bar{K}}_n$.

Theorem 2.11. Let G be a bistar graph $S_{k_1\mathrm{,}{k}_1}$ with $n=2k_1+2$ vertices. Then, $UP\left(G,x\right)=x^{2k_1}{\left(1+x\right)}^2$. Furthermore, $Z_{up}\left(G\right)=\left\{\mathrm{0,}-1\right\}$.

Proof. Let G be a bistar graph $S_{k_1\mathrm{,}{k}_1}$ with $n=2k_1+2$ vertices, we have ${\gamma }_{up}\left(G\right)=2k_1$. Then, there is only one UDS of size $2k_1$ and for $i=2k_1+1$ there are two UDS. Finally, for $i=2k_1+2=n$ there is only one UDS. Thus, the result will be as following

$\begin{array}{c}UP\left(G,x\right)=x^{2k_1}+2x^{2k_1+1}+x^{2k_1+2}\\ =x^{2k_1}\left[1+2x+x^2\right]\\ =x^{2k_1}{\left(1+x\right)}^2.\end{array}$

Theorem 2.12. For any graph $G\cong K_{r\mathrm{,}s}$ with $r<s$ and $r+s\ge 3$ vertices, $UP\left(G\mathrm{,}x\right)=x^s{\left(1+x\right)}^r$. Furthermore, $Z_{up}\left(K_{r\mathrm{,}s}\right)=\left\{\mathrm{0,}-1\right\}$.

Proof. Let G is a complete bipartite graph $K_{r\mathrm{,}s}$ with $r<s$, then we have ${\gamma }_{up}\left(K_{r\mathrm{,}s}\right)=s$. There is only one UDS of size s. Now, for $i=s+1$ there exist r UDS. For $i=s+2$ there exist $\left(\begin{array}{c}r\\ 2\end{array}\right)$ UDS and so on. Thus, we get

$\begin{array}{c}UP\left(G,x\right)=x^s+\left(\begin{array}{c}r\\ 1\end{array}\right)x^{s+1}+\left(\begin{array}{c}r\\ 2\end{array}\right)x^{s+2}+\cdots +\left(\begin{array}{c}r\\ r\end{array}\right)x^{s+r}\\ =x^s+{\displaystyle \underset{i=1}{\overset{r}{\sum }}}\left(\begin{array}{c}r\\ i\end{array}\right)x^{s+i}\\ =x^s\left[{\displaystyle \underset{i=0}{\overset{r}{\sum }}}\left(\begin{array}{c}r\\ i\end{array}\right)x^i\right]\\ =x^s{\left(1+x\right)}^r.\end{array}$

Corollary 2.13. For any graph $G\cong S_r$ with $r+1$ vertices, $UP\left(G,x\right)=x^r\left(1+x\right)$. Furthermore, $Z_{up}\left(G\right)=\left\{\mathrm{0,}-1\right\}$.

The generalization of Theorem 0.12 is the following result.

Theorem 2.14. For any graph $G\cong K_{r_1\mathrm{,}\cdots ,r_k}$ where $r_1<r_2<\cdots <r_k$ with $n={\displaystyle {\sum }_{i=1}^k}{r}_i$ vertices, $UP\left(G\mathrm{,}x\right)=x^{r_k}{\left(1+x\right)}^{n-r_k}$. Furthermore, $Z_{up}\left(K_{r_1\mathrm{,}\cdots ,r_k}\right)=\left\{\mathrm{0,}-1\right\}$.

Proof. Let G be a complete k-partite graph $K_{r_1\mathrm{,}\cdots ,r_k}$ with $r_1<r_2<\cdots <r_k$, we have ${\gamma }_{up}\left(K_{r_1,\cdots ,r_k}\right)=r_k$. There is only one UDS of size $r_k$ for $i=r_k+1$ there are $n-r_k$ UDS of size $r_k+1$. Also, for $i=r_k+2$ there are $\left(\begin{array}{c}n-r_k\\ 2\end{array}\right)$ and so on. Thus,

$\begin{array}{c}UP\left(G,x\right)=x^{r_k}+\left(\begin{array}{c}n-r_k\\ 1\end{array}\right)x^{r_k+1}+\left(\begin{array}{c}n-r_k\\ 2\end{array}\right)x^{r_k+2}+\cdots +\left(\begin{array}{c}n-r_k\\ n-r_k\end{array}\right)x^n\\ =x^{r_k}+{\displaystyle \underset{i=1}{\overset{n-r_k}{\sum }}}\left(\begin{array}{c}n-r_k\\ i\end{array}\right)x^{r_k+i}\\ =x^{r_k}\left[{\displaystyle \underset{i=0}{\overset{n-r_k}{\sum }}}\left(\begin{array}{c}n-r_k\\ i\end{array}\right)x^i\right]\\ =x^{r_k}{\left(1+x\right)}^{n-r_k}.\end{array}$

Proposition 2.15. For any graph $G\cong K_{r_1\mathrm{,}{r}_2\mathrm{,}\cdots \mathrm{,}{r}_k}$ with $n={\displaystyle {\sum }_{i=1}^k}{r}_i$ vertices we have the following:

1) If $r_1\le r_2\le \cdots \le r_{k-1}<r_k$, such that at least two partite sets of the same size, then $UP\left(G\mathrm{,}x\right)=x^{r_k}{\left(1+x\right)}^{n-r_k}$.

2) If $r_1=r_2=\cdots =r_k$, then the graph is regular and $UP\left(G,x\right)={\left(1+x\right)}^n-1$.

Theorem 2.16. For any graph $G\cong K_{r_1\mathrm{,}{r}_2\mathrm{,}\cdots \mathrm{,}{r}_k}$ with $n={\displaystyle {\sum }_{i=1}^k}{r}_i$ vertices, where $r_1\le r_2\le \cdots <r_{k-1}=r_k$. Then,

$UP\left(G,x\right)={\displaystyle \underset{h=1}{\overset{n}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1\ge 1\\ r_1+r_2=h\end{array}}{\sum }}\left(\begin{array}{c}2r_k\\ r_1\end{array}\right)\left(\begin{array}{c}n-2r_k\\ r_2\end{array}\right)\right]x^h.$

Proof. Let G be a complete k-partite graph $K_{r_1\mathrm{,}\cdots ,r_k}$ with $r_1\le r_2\le \cdots <r_{k-1}=r_k$, then we have ${\gamma }_{up}\left(K_{r_1\mathrm{,}\cdots ,r_k}\right)=1$. Let divide the vertices of a graph into two sets $R_1$ and $R_2$ where $R_1$ contains the vertices of $r_k$ and $r_{k-1}$ which means $R_1$ is of cardinality $2r_k$ while $R_2=V\left(G\right)\backslash R_1$ this implies that $R_2$ is of cardinality $n-2r_k$. Thus, we get

$up\left(G,1\right)=\left(\begin{array}{c}2r_k\\ 1\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 0\end{array}\right)=2r_k.$

We have for $up\left(G\mathrm{,2}\right)$,

$up\left(G,2\right)=\left(\begin{array}{c}2r_k\\ 2\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 0\end{array}\right)+\left(\begin{array}{c}2r_k\\ 1\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 1\end{array}\right).$

Also, for $up\left(G\mathrm{,3}\right)$ we get

$up\left(G\mathrm{,3}\right)=\left(\begin{array}{c}2r_k\\ 3\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 0\end{array}\right)+\left(\begin{array}{c}2r_k\\ 2\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 1\end{array}\right)+\left(\begin{array}{c}2r_k\\ 1\end{array}\right)\left(\begin{array}{c}n-2r_k\\ 2\end{array}\right)\mathrm{.}$

And so on we get for all $up\left(G\mathrm{,}h\right)$, where $1\le h\le n$

$up\left(G,h\right)={\displaystyle \underset{\begin{array}{c}{r}_1\ge 1\\ r_1+r_2=h\end{array}}{\sum }}\left(\begin{array}{c}2r_k\\ r_1\end{array}\right)\left(\begin{array}{c}n-2r_k\\ r_2\end{array}\right).$

Thus, the proof is done.

Theorem 2.17. For any graph $G\cong W_s$ with $s+1$ vertices and $s>3$, then $UP\left(G\mathrm{,}x\right)=\left(1+x\right)\left[{\left(1+x\right)}^s-1\right]$.

Proof. Let G be a wheel graph $W_s$ ( $s>3$ ), then we have ${\gamma }_{up}\left(W_s\right)=1$. There are s UDS of size one. For $i=2$ there are $\left(\begin{array}{c}s+1\\ 2\end{array}\right)$ UDS of size two and so on. Thus,

$\begin{array}{c}UP\left(G,x\right)=sx+\left(\begin{array}{c}s+1\\ 2\end{array}\right)x^2+\left(\begin{array}{c}s+1\\ 3\end{array}\right)x^3+\cdots +\left(\begin{array}{c}s+1\\ s+1\end{array}\right)x^{s+1}\\ =\left[{\displaystyle \underset{i=0}{\overset{s+1}{\sum }}}\left(\begin{array}{c}s+1\\ i\end{array}\right)x^i\right]-\left(x+1\right)\\ ={\left(x+1\right)}^{s+1}-\left(x+1\right)\\ =\left(x+1\right)\left[{(x+1)}^s-1\right].\end{array}$

Corollary 2.18. For any wheel graph $W_s$ and $s>3$ we have

$Z_{up}\left(W_s\right)=\{\begin{array}{l}\left\{0,-1,-2\right\},\text{if}s\text{is}\text{even}.\\ \left\{0,-1\right\},\text{if}s\text{is}\text{odd}.\end{array}$

3. Uphill Domination Polynomials of Graphs under Some Binary Operations

Theorem 3.1. Let $G\cong P_r\times P_s$ be a grid graph with rs vertices and $r\mathrm{,}s\ge 4$. Then, $UP\left(G\mathrm{,}x\right)=x^4{\left(1+x\right)}^{rs-4}$.

Proof. Let G be a grid graph with rs vertices and $r\mathrm{,}s\ge 4$, then we have ${\gamma }_{up}\left(G\right)=4$. Note that, there is only one UDS of size four. For $i=5$, there are $rs-4$ UDS of size five and so on. Thus, we get

$\begin{array}{c}UP\left(G,x\right)=x^4+\left(\begin{array}{c}rs-4\\ 1\end{array}\right)x^5+\cdots +\left(\begin{array}{c}rs-4\\ rs-4\end{array}\right)x^{rs}\\ =x^4\left[{\displaystyle \underset{i=0}{\overset{rs-4}{\sum }}}\left(\begin{array}{c}rs-4\\ i\end{array}\right)x^i\right]\\ =x^4{\left(1+x\right)}^{rs-4}.\end{array}$

Theorem 3.2. Let $G\cong C_r\circ {\bar{K}}_s$ be a corona graph with $rs+r$ vertices. Then, $UP\left(G\mathrm{,}x\right)=x^{rs}{\left(1+x\right)}^r$.

Proof. Let $G\cong C_r\circ {\bar{K}}_s$ with $rs+r$ vertices, we have ${\gamma }_{up}\left(C_r\circ {\bar{K}}_s\right)=rs$. For rs vertices, there is only one UDS of size rs. For $rs+1$ vertices, there are r UDS and so on. Thus, we get

$\begin{array}{c}UP\left(G,x\right)=x^{rs}+\left(\begin{array}{c}r\\ 1\end{array}\right)x^{rs+1}+\cdots +\left(\begin{array}{c}r\\ r\end{array}\right)x^{rs+r}\\ ={\displaystyle \underset{i=0}{\overset{r}{\sum }}}\left(\begin{array}{c}r\\ i\end{array}\right)x^{rs+i}\\ =x^{rs}\left[{\displaystyle \underset{i=0}{\overset{r}{\sum }}}\left(\begin{array}{c}r\\ i\end{array}\right)x^i\right]\\ =x^{rs}{\left(1+x\right)}^r.\end{array}$

Corollary 3.3. Let $G\cong C_r\circ K_1$ be a corona graph with 2r vertices. Then, $UP\left(G\mathrm{,}x\right)=x^r{\left(1+x\right)}^r$.

Theorem 3.2 can generalize in the following result.

Theorem 3.4. For any nontrivial connected graph H with r vertices, if $G\cong H\circ {\bar{K}}_s$, then, $UP\left(G\mathrm{,}x\right)=x^{rs}{\left(1+x\right)}^r$.

Proof. The proof similarly to the proof of Theorem 3.2.

Theorem 3.5. Let G be a book graph $B_m=P_2\times S_m$ with $2m+2$ vertices. Then,

$\begin{array}{c}UP\left(G,x\right)=2^m{x}^m+\left[m\left(2^{m-1}\right)+2^{m+1}\right]x^{m+1}\\ +{\displaystyle \underset{i=2}{\overset{2m-1}{\sum }}}\left[\left(\begin{array}{c}m\\ i\end{array}\right)2^{m-i}+\left(\begin{array}{c}m\\ i-1\end{array}\right)2^{m-i+2}+\left(\begin{array}{c}m\\ i-2\end{array}\right)2^{m-i+2}\right]x^{m+i}\\ +\left[1+m{2}^2+\left(\begin{array}{c}m\\ 2\end{array}\right)2^2\right]x^{2m}+\left(2m+2\right)x^{2m+1}+x^{2m+2}.\end{array}$

Proof. Suppose we have the book graph $B_m=P_2\times S_m$ with $2m+2$ vertices, then we have ${\gamma }_{up}\left(P_2\times S_m\right)=m$. Let divide the vertices of $B_m$ into $m+1$ sets “as shown in Figure 2” let the set $R_i=\left\{u_i\mathrm{,}{v}_i\right\}$ i.e., $1\le i\le m$ while $R_{m+1}=\left\{u\mathrm{,}v\right\}$. Since ${\gamma }_{up}\left(P_2\times S_m\right)=m$, then for $up\left(G\mathrm{,}m\right)$ we have to take one vertex from each $R_i$ ( $i\ne m+1$ ) so, there exist $2^m$ UDS of size m. For $up\left(G\mathrm{,}m+1\right)$ we have,

$\begin{array}{c}up\left(G\mathrm{,}m+1\right)=\underset{\left(m+1\right)\text{times}}{\underset{︸}{\left(\begin{array}{c}2\\ 1\end{array}\right)\cdots \left(\begin{array}{c}2\\ 1\end{array}\right)}}+{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+1\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 0\end{array}\right)\\ =2^{m+1}+m\left(2^{m-1}\right)\mathrm{.}\end{array}$

Also, for $up\left(G\mathrm{,}m+2\right)$ we get

$\begin{array}{c}up\left(G,m+2\right)={\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+2\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 0\end{array}\right)+{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+1\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 1\end{array}\right)\\ +{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 2\end{array}\right)\\ =\left(\begin{array}{c}m\\ 2\end{array}\right)2^{m-2}+\left(\begin{array}{c}m\\ 1\end{array}\right)2^m+\left(\begin{array}{c}m\\ 0\end{array}\right)2^m\\ =\left(\begin{array}{c}m\\ 2\end{array}\right)2^{m-2}+m{2}^m+2^m.\end{array}$

Figure 2. A Book Graph B_m.

Therefore, for $up\left(G\mathrm{,}m+3\right)$ we have

$\begin{array}{c}up\left(G,m+3\right)={\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+3\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 0\end{array}\right)+{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+2\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 1\end{array}\right)\\ +{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=m+1\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 2\end{array}\right)\\ =\left(\begin{array}{c}m\\ 3\end{array}\right)2^{m-3}+\left(\begin{array}{c}m\\ 2\end{array}\right)2^m+\left(\begin{array}{c}m\\ 1\end{array}\right)2^m\\ =\left(\begin{array}{c}m\\ 3\end{array}\right)2^{m-3}+\left(\begin{array}{c}m\\ 2\end{array}\right)2^m+m{2}^m.\end{array}$

And so on, we use the same argument until $up\left(G\mathrm{,2}m-1\right)$. After that, for $up\left(G\mathrm{,2}m\right)$ we have

$\begin{array}{c}up\left(G,2m\right)=\left(\begin{array}{c}2\\ 2\end{array}\right)\cdots \left(\begin{array}{c}2\\ 2\end{array}\right)\left(\begin{array}{c}2\\ 0\end{array}\right)+{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=2m-1\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 1\end{array}\right)\\ +{\displaystyle \underset{\begin{array}{c}{\displaystyle \sum r_i}=2m-2\\ r_1\cdots \mathrm{,}{r}_m\ge 1\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_m\end{array}\right)\left(\begin{array}{c}2\\ 2\end{array}\right)\\ =1+m{2}^2+\left(\begin{array}{c}m\\ 2\end{array}\right)2^2.\end{array}$

Finally,

$up\left(G,2m+1\right)=\left(\begin{array}{c}2m+2\\ 2m+1\end{array}\right)=2m+2\&up\left(G,2m+2\right)=1.$

Thus, the proof is completed.

Theorem 3.6. Let G be a graph. If $G\cong P_k\times C_s$ with sk vertices, then

$UP\left(G,x\right)={\displaystyle \underset{t=2}{\overset{sk}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1,r_2\ge 1\\ r_1+r_2+r_3=t\end{array}}{\sum }}\left(\begin{array}{c}s\\ r_1\end{array}\right)\left(\begin{array}{c}s\\ r_2\end{array}\right)\left(\begin{array}{c}sk-2s\\ r_3\end{array}\right)\right]x^t.$

Proof. Let $G\cong P_k\times C_s$ with sk vertices, then we have ${\gamma }_{up}\left(P_k\times C_s\right)=2$. We first divide the vertices of G into three sets called them $R_1\mathrm{,}{R}_2$ and $R_3$, where $R_1$ (resp. $R_2$ ) is contains the vertices of the outer cycle (resp. inner cycle) which every vertex is of degree three. The third set $R_3$ contains the vertices of the middle cycles, where every vertex is of degree four. Note that, any UDS should contain at least one vertex form $R_1$ and one vertex from $R_2$. Thus, for $up(\; G\; ,2\; )$

$up\left(G,2\right)=\left(\begin{array}{c}s\\ 1\end{array}\right)\left(\begin{array}{c}s\\ 1\end{array}\right)\left(\begin{array}{c}sk-2s\\ 0\end{array}\right)=s^2.$

For $up\left(G,3\right)$ we have

$up\left(G,3\right)={\displaystyle \underset{\begin{array}{c}{r}_1,r_2\ge 1\\ r_1+r_2+r_3=3\end{array}}{\sum }}\left(\begin{array}{c}s\\ r_1\end{array}\right)\left(\begin{array}{c}s\\ r_2\end{array}\right)\left(\begin{array}{c}sk-2s\\ r_3\end{array}\right).$

And so on, we use the same argument for all $up\left(G\mathrm{,}t\right)$ i.e., $3\le t\le sk$ and the proof is done.

Theorem 3.7. Let G ba a tadpole graph $T_{s\mathrm{,}k}$ with $s+k$ vertices. Then,

$UP\left(G,x\right)=\left(s-1\right)x^2+{\displaystyle \underset{t=3}{\overset{s+k}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1+r_2=t-1\\ r_2\ge 1\end{array}}{\sum }}\left(\begin{array}{c}k\\ r_1\end{array}\right)\left(\begin{array}{c}s-1\\ r_2\end{array}\right)\right]x^t.$

Proof. Let G be a tadpole graph $T_{s\mathrm{,}k}$ with $s+k$ vertices, we have ${\gamma }_{up}\left(T_{s\mathrm{,}k}\right)=2$. We first divide the vertices of $T_{s\mathrm{,}k}$ into three sets called them $R_1\mathrm{,}{R}_2$ and $R_3$ such that $R_1$ is a singleton set that contains the pendant vertex, $R_2$ has k vertices each of them is of degree two except one vertex is of degree three while the last set $R_3$ has $s-1$ vertices each of them of degree two which are the vertices that lies in a cycle part of a graph. Notice that, any UDS of $T_{s\mathrm{,}k}$ should contains the pendant vertex and at least one vertex from $R_3$. Now, for $up\left(G\mathrm{,2}\right)$ we have to take the pendant vertex with one vertex from $R_3$, so there exist $s-1$ UDS of size two. For $up\left(G\mathrm{,3}\right)$ we get

$up\left(G,3\right)={\displaystyle \underset{\begin{array}{c}{r}_3\ge 1\\ r_2+r_3=2\end{array}}{\sum }}\left(\begin{array}{c}k\\ r_2\end{array}\right)\left(\begin{array}{c}s-1\\ r_3\end{array}\right).$

And so on, we use the same argument for all $up\left(G\mathrm{,}t\right)$ i.e., $3\le t\le s+k$ and the proof is completed.

Theorem 3.8. Let G be a windmill graph $Wd\left(s\mathrm{,}k\right)$ with $k\left(s-1\right)+1$ vertices. Then,

$UP\left(G,x\right)={\left(s-1\right)}^k{x}^k+{\displaystyle \underset{t=k+1}{\overset{k\left(s-1\right)+1}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1,\cdots ,r_k\ge 1\\ r_1+\cdots +r_{k+1}=t\end{array}}{\sum }}\left(\begin{array}{c}s-1\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}s-1\\ r_k\end{array}\right)\left(\begin{array}{c}1\\ r_{k+1}\end{array}\right)\right]x^t.$

Proof. Let G be a windmill graph with center vertex w, we have ${\gamma }_{up}\left(G\right)=k$. Any minimum uphill domination set must contains one vertex from each copy of $K_s$ without the center vertex w, that means, we have ${\left(s-1\right)}^k$ uphill dominating set of size k. Suppose $R_i$ be the set of vertices of the i-th copy of $K_S$ without the center vertex w and $R_w$ be the singleton, with the center vertex w. To get the number of uphill dominating sets of size $t=k+j$, where $j\mathrm{<mo>\; =\; </mo>1,2,}\cdots ,\left(k\left(s-2\right)+1\right)$, we need to select $r_i$ vertices from each $R_i$, and $r_{k+1}$ from $R_w$ where $i=1,2,\cdots ,k$, ${\displaystyle {\sum }_{i=1}^{k+1}}{r}_i=t$ and $r_i\ge 1$ for all $i=1,2,\cdots ,k$. Hence,

$up\left(G,t\right)={\displaystyle \underset{\begin{array}{c}{r}_1,\cdots ,r_k\ge 1\\ r_1+\cdots +r_{k+1}=t\end{array}}{\sum }}\left[\left(\begin{array}{c}s-1\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}s-1\\ r_k\end{array}\right)\left(\begin{array}{c}1\\ r_{k+1}\end{array}\right)\right].$

Thus,

$UP\left(G,x\right)={\left(s-1\right)}^k{x}^k+{\displaystyle \underset{t=k+1}{\overset{k\left(s-1\right)+1}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1,\cdots ,r_k\ge 1\\ r_1+\cdots +r_{k+1}=t\end{array}}{\sum }}\left(\begin{array}{c}s-1\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}s-1\\ r_k\end{array}\right)\left(\begin{array}{c}1\\ r_{k+1}\end{array}\right)\right]x^t.$

Proposition 3.9. Let G be a dutch windmill graph $D\left(s\mathrm{,}k\right)$ with $s>3$ and $k\left(s-1\right)+1$ vertices. Then,

$UP\left(D\left(s\mathrm{,}k\right)\mathrm{,}x\right)=UP\left(Wd\left(s\mathrm{,}k\right)\mathrm{,}x\right)\mathrm{.}$

Theorem 3.10. Let G be a firefly graph $F_{s\mathrm{,}t\mathrm{,}k}$ with $s\mathrm{,}t\mathrm{,}k\ge 0$, $n=2s+2t+k+1$ vertices and ${\gamma }_{up}\left(G\right)=s+t+k=b$. Then,

$\begin{array}{c}Up\left(G,x\right)=2^s{x}^b+\left[2^s\left(t+1\right)+2^{s-1}\left(s\right)\right]x^{b+1}\\ +{\displaystyle \underset{h=b+2}{\overset{n}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1,\cdots ,r_s\ge 1\\ r_1+\cdots +r_{s+1}=h-\left(t+k\right)\end{array}}{\sum }}\left(\begin{array}{c}s\\ r_1\end{array}\right)\left(\begin{array}{c}s\\ r_2\end{array}\right)\cdots \left(\begin{array}{c}s\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ r_{s+1}\end{array}\right)\right]x^h.\end{array}$

Proof. Let G be a firefly graph $F_{s\mathrm{,}t\mathrm{,}k}$ with n vertices and ${\gamma }_{up}\left(G\right)=s+t+k=b$. First, let us divide the vertices of G into $s+2$ sets and let u be the shared vertex in G. Suppose that $R_1\subset V\left(G\right)$ contains the vertices of the first triangle without u, this implies $R_1$ has two vertices each of them are of degree two, also we mean by $R_2\subset V\left(G\right)$ the set that contains the vertices of the second triangle without u and so on for all $R_i$, where $1\le i\le s$. Now, the subset $R_{s+1}\subset V\left(G\right)$ contains u in addition the t vertices of the pendant paths that adjacent to u which means $R_{s+1}$ is of cardinality $t+1$. Finally, $R_{s+2}\subset V\left(G\right)$ contains all the leaves vertices of G which be exactly of cardinality $t+k$. Notice that, any UDS of G should contain all the vertices of $R_{s+2}$ with at least one vertex from each $R_i$. Thus, for $up\left(G\mathrm{,}b\right)$ we have

$\begin{array}{c}up\left(G,b\right)={\displaystyle \underset{\begin{array}{c}{\displaystyle {\sum }_{i=1}^{s+2}{r}_i}=b\end{array}}{\sum }}\left[\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ r_{s+1}\end{array}\right)\left(\begin{array}{c}t+k\\ r_{s+2}\end{array}\right)\right]\\ =\left[\left(\begin{array}{c}2\\ 1\end{array}\right)\cdots \left(\begin{array}{c}2\\ 1\end{array}\right)\left(\begin{array}{c}t+1\\ 0\end{array}\right)\left(\begin{array}{c}t+k\\ t+k\end{array}\right)\right]\\ =\underset{s\text{times}}{\underset{︸}{2\times 2\times \cdots \times 2}}=2^s.\end{array}$

For $up\left(G\mathrm{,}b+1\right)$ we get

$\begin{array}{c}up\left(G,b+1\right)={\displaystyle \underset{\begin{array}{c}{\displaystyle {\sum }_{i=1}^{s+2}{r}_i}=b+1\end{array}}{\sum }}\left[\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ r_{s+1}\end{array}\right)\left(\begin{array}{c}t+k\\ t+k\end{array}\right)\right]\\ ={\displaystyle \underset{\begin{array}{c}{\displaystyle {\sum }_{i=1}^{s+1}{r}_i}=\left(b+1\right)-\left(t+k\right)\end{array}}{\sum }}\left[\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ 0\end{array}\right)\right]+\underset{s\text{times}}{\underset{︸}{\left(\begin{array}{c}2\\ 1\end{array}\right)\cdots \left(\begin{array}{c}2\\ 1\end{array}\right)}}\left(\begin{array}{c}t+1\\ 1\end{array}\right)\\ =2^{s-1}\left(s\right)+2^s\left(t+1\right).\end{array}$

And for $up\left(G\mathrm{,}b+2\right)$ we have

$\begin{array}{c}up\left(G,b+2\right)={\displaystyle \underset{\begin{array}{c}{\displaystyle {\sum }_{i=1}^{s+2}{r}_i}=b+2\end{array}}{\sum }}\left[\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ r_{s+1}\end{array}\right)\left(\begin{array}{c}t+k\\ t+k\end{array}\right)\right]\\ ={\displaystyle \underset{\begin{array}{c}{\displaystyle {\sum }_{i=1}^{s+1}{r}_i}=\left(b+2\right)-\left(t+k\right)\end{array}}{\sum }}\left[\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_s\end{array}\right)\left(\begin{array}{c}t+1\\ r_{s+1}\end{array}\right)\right].\end{array}$

In the same argument we can find all $up\left(G\mathrm{,}h\right)$, where $b+2\le h\le n$ and the proof is completed.

Corollary 3.11. Let G be a friendship graph $F_k$ with $2k+1$ vertices. Then,

$UP\left(G,x\right)=2^k{x}^k+\left[2^k+k{2}^{k-1}\right]x^{k+1}+{\displaystyle \underset{t=k+2}{\overset{2k+1}{\sum }}}\left[{\displaystyle \underset{\begin{array}{c}{r}_1,\cdots ,r_k\ge 1\\ r_1+\cdots +r_{k+1}=t\end{array}}{\sum }}\left(\begin{array}{c}2\\ r_1\end{array}\right)\cdots \left(\begin{array}{c}2\\ r_k\end{array}\right)\left(\begin{array}{c}1\\ r_{k+1}\end{array}\right)\right]x^t.$

4. Open Problems

Finally, for feature work we state the following definition.

Definition 4.1. Two graphs G and H are said to be uphill-equivalent if $UP\left(G\mathrm{,}x\right)=UP\left(H\mathrm{,}x\right)$. The uphill-equivalence classes of G noted by ${\left[G\right]}_{up}=\left\{H\mathrm{<mo>\; :\; </mo>}H\text{is}\text{uphill-equivalent}\text{to}G\right\}$.

Example 4.2.

1) ${\left[K_n\right]}_{up}=\left\{H\mathrm{<mo>\; :\; </mo>}H\text{is}\text{regular}\text{graph}\text{of}n\text{vertices}\right\}$.

2) The windmill graph $Wd\left(s\mathrm{,}k\right)$ and Dutch windmill graph $D\left(s\mathrm{,}k\right)$ are uphill-equivalent.

We state the following open problems for feature work:

1) which graphs have two distinct uphill domination roots?

2) which families of graphs have only real uphill domination roots?

3) which graphs satisfy ${\left[G\right]}_{up}=\left\{G\right\}$ ?

4) determine the uphill-equivalence classes for some new families of graphs.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Deering, J. (2013) Uphill & Downhill Domination in Graphs and Related Graph Parameters. Thesis, East Tennessee State University, Johnson.
[2]	Balakrishnan, R. and Ranganathan, K. (2012) A Textbook of Graph Theory. Springer Science & Business Media, New York. https://doi.org/10.1007/978-1-4614-4529-6
[3]	Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.
[4]	Hedetniemi, S.T., Haynes, T.W., Jamieson, J.D. and Jamieson, W.B. (2014) Downhill Domination in Graphs. Discussiones Mathematicae, Graph Theory, 34, 603-612. https://doi.org/10.7151/dmgt.1760
[5]	Alikhani, S. and Peng, Y.H. (2009) Introduction to Domination Polynomial of a Graph. Ars Combinatoria, 114. arXiv:0905.2251
[6]	Alsalomy, T., Saleh, A., Muthana, N. and Al shammakh, W. On the Uphill Domination Number of Graphs. (Submitted)