On the Uphill Domination Polynomial of Graphs

摘要

A path π = [v1, v2, …, vk] in a graph G = (V, E) is an uphill path if deg(vi) ≤ deg(vi+1) for every 1 ≤ i ≤ k. A subset S ⊆ V(G) is an uphill dominating set if every vertex vi ∈ 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.