TITLE:
On the Uphill Domination Polynomial of Graphs
AUTHORS:
Thekra Alsalomy, Anwar Saleh, Najat Muthana, Wafa Al Shammakh
KEYWORDS:
Domination, Uphill Domination, Uphill Domination Polynomial
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.8 No.6,
June
23,
2020
ABSTRACT: 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.