In this paper, we are concerned with simple graphs which are finite, undirected with no loops nor multiple edges. Throughout this paper, we let and . In a graph , the degree of denoted by 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 we have .
The bistar graph with vertices is obtained by joining the non-pendant vertices of two copies of star graph by new edge. The corona of two graphs and with and vertices, respectively, denoted by is obtained by taking one copy of and copies of and joining the ith vertex of with an edge to every vertex in the ith copy of . The corona (in particular) is the graph constructed by a copy of G, where for each vertex a new vertex and a pendant edge are added. The tadpole graph is a graph consisting of a cycle graph on at least three vertices and a path graph on k vertices connected with bridge. The wheel graph is a graph formed by connecting a single vertex to all vertices of a cycle graph . The book graph is a Cartesian product , where is the star graph with vertices and is the path graph on two vertices. Also, the windmill graph is a graph constructed for and by joining k copies of the complete graph at a shared universal vertex. The dutch windmill graph is the graph obtained by taking k copies of the cycle graph with a vertex in common. Also, the friendship is a graph that constructed by joining k copies of the cycle graph and observes that is a special case of . Finlay, the firefly graph with and 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 .
A set of vertices in a graph G is called a dominating set if every vertex is either or v is adjacent to an element of S, The uphill dominating set “UDS” is a set having the property that every vertex lies on an uphill path originating from some vertex in S. The uphill domination number of a graph G is denoted by 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 -set, for more details in domination see  and .
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  and the uphill domination of a graph , 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
where is the number of uphill dominating sets of size i in G. The set of roots of is called uphill domination roots of graph G and denoted by .
Example 2.2. The uphill domination polynomial of House graph H (as shown in Figure 1) with 6 vertices and is given by . Furthermore, .
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 vertices. Then, if and only if G is r-regular graph.
Proof. Let G be a connected graph of vertices. Suppose that the uphill domination polynomial of G is given by
Since the first coefficient of the polynomial is n, then it is easily verified that for every , the singleton vertex set is an UDS in G. Assume that G is not r-regular graph. Hence there exists a vertex such that . Now, we have two cases:
Case 1: If , then the set is not UDS which contradict that every singleton vertex set is an UDS in G.
Case 2: If , then for all with , we get the set 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 vertices. We have , then there exist n UDS of size one, while for there are UDS and so on. Thus, we can write the uphill domination polynomial as
Corollary 2.4. Let G ba a graph with s vertices. If G is a cycle or complete graph , then .
Corollary 2.5. The uphill domination polynomial for the regular graph with sk vertices is given by .
Corollary 2.6.  Let G be a graph with m components. Then,
Proposition 2.7. If a graph G with n vertices consists of m components , then
Figure 1. The House graph.
Proof. By using mathematical induction we found that for the statement is true and the proof is trivial. Suppose that the statement is true when such that
Now, we prove that the statement is true when . Let G consists of components that mean . If the set represent the uphill domination number for the components of G respectively, such that . Then, by Corollary (2.6) it easily to see that
Thus, is exactly equal the number of way for choosing an UDS of size in and an UDS of size in and so on. Hence, is the coefficient of in and in . In the same argument we can proof for all , where that
Thus, for the statement is true and the proof is done.
Theorem 2.8. For any path with vertices, . Furthermore, .
Proof. Let G be a path graph with . We know that , then there is only one UDS of size two. For there are UDS of size three and so on. Thus, we get
Theorem 2.9. For any graph G. if and only if .
Proof. Let G be a graph with . Since, , then we can write that
Thus, . On the other hand if , then by Proposition (2.7) we get .
Corollary 2.10. A graph G has one uphill domination root if and only if .
Theorem 2.11. Let G be a bistar graph with vertices. Then, . Furthermore, .
Proof. Let G be a bistar graph with vertices, we have . Then, there is only one UDS of size and for there are two UDS. Finally, for there is only one UDS. Thus, the result will be as following
Theorem 2.12. For any graph with and vertices, . Furthermore, .
Proof. Let G is a complete bipartite graph with , then we have . There is only one UDS of size s. Now, for there exist r UDS. For there exist UDS and so on. Thus, we get
Corollary 2.13. For any graph with vertices, . Furthermore, .
The generalization of Theorem 0.12 is the following result.
Theorem 2.14. For any graph where with vertices, . Furthermore, .
Proof. Let G be a complete k-partite graph with , we have . There is only one UDS of size for there are UDS of size . Also, for there are and so on. Thus,
Proposition 2.15. For any graph with vertices we have the following:
1) If , such that at least two partite sets of the same size, then .
2) If , then the graph is regular and .
Theorem 2.16. For any graph with vertices, where . Then,
Proof. Let G be a complete k-partite graph with , then we have . Let divide the vertices of a graph into two sets and where contains the vertices of and which means is of cardinality while this implies that is of cardinality . Thus, we get
We have for ,
Also, for we get
And so on we get for all , where
Thus, the proof is done.
Theorem 2.17. For any graph with vertices and , then .
Proof. Let G be a wheel graph ( ), then we have . There are s UDS of size one. For there are UDS of size two and so on. Thus,
Corollary 2.18. For any wheel graph and we have
3. Uphill Domination Polynomials of Graphs under Some Binary Operations
Theorem 3.1. Let be a grid graph with rs vertices and . Then, .
Proof. Let G be a grid graph with rs vertices and , then we have . Note that, there is only one UDS of size four. For , there are UDS of size five and so on. Thus, we get
Theorem 3.2. Let be a corona graph with vertices. Then, .
Proof. Let with vertices, we have . For rs vertices, there is only one UDS of size rs. For vertices, there are r UDS and so on. Thus, we get
Corollary 3.3. Let be a corona graph with 2r vertices. Then, .
Theorem 3.2 can generalize in the following result.
Theorem 3.4. For any nontrivial connected graph H with r vertices, if , then, .
Proof. The proof similarly to the proof of Theorem 3.2.
Theorem 3.5. Let G be a book graph with vertices. Then,
Proof. Suppose we have the book graph with vertices, then we have . Let divide the vertices of into sets “as shown in Figure 2” let the set i.e., while . Since , then for we have to take one vertex from each ( ) so, there exist UDS of size m. For we have,
Also, for we get
Figure 2. A Book Graph Bm.
Therefore, for we have
And so on, we use the same argument until . After that, for we have
Thus, the proof is completed.
Theorem 3.6. Let G be a graph. If with sk vertices, then
Proof. Let with sk vertices, then we have . We first divide the vertices of G into three sets called them and , where (resp. ) is contains the vertices of the outer cycle (resp. inner cycle) which every vertex is of degree three. The third set 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 and one vertex from . Thus, for
For we have
And so on, we use the same argument for all i.e., and the proof is done.
Theorem 3.7. Let G ba a tadpole graph with vertices. Then,
Proof. Let G be a tadpole graph with vertices, we have . We first divide the vertices of into three sets called them and such that is a singleton set that contains the pendant vertex, has k vertices each of them is of degree two except one vertex is of degree three while the last set has 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 should contains the pendant vertex and at least one vertex from . Now, for we have to take the pendant vertex with one vertex from , so there exist UDS of size two. For we get
And so on, we use the same argument for all i.e., and the proof is completed.
Theorem 3.8. Let G be a windmill graph with vertices. Then,
Proof. Let G be a windmill graph with center vertex w, we have . Any minimum uphill domination set must contains one vertex from each copy of without the center vertex w, that means, we have uphill dominating set of size k. Suppose be the set of vertices of the i-th copy of without the center vertex w and be the singleton, with the center vertex w. To get the number of uphill dominating sets of size , where , we need to select vertices from each , and from where , and for all . Hence,
Proposition 3.9. Let G be a dutch windmill graph with and vertices. Then,
Theorem 3.10. Let G be a firefly graph with , vertices and . Then,
Proof. Let G be a firefly graph with n vertices and . First, let us divide the vertices of G into sets and let u be the shared vertex in G. Suppose that contains the vertices of the first triangle without u, this implies has two vertices each of them are of degree two, also we mean by the set that contains the vertices of the second triangle without u and so on for all , where . Now, the subset contains u in addition the t vertices of the pendant paths that adjacent to u which means is of cardinality . Finally, contains all the leaves vertices of G which be exactly of cardinality . Notice that, any UDS of G should contain all the vertices of with at least one vertex from each . Thus, for we have
For we get
And for we have
In the same argument we can find all , where and the proof is completed.
Corollary 3.11. Let G be a friendship graph with vertices. Then,
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 . The uphill-equivalence classes of G noted by .
2) The windmill graph and Dutch windmill graph 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 ?
4) determine the uphill-equivalence classes for some new families of graphs.