On the Uphill Domination Polynomial of Graphs

• 作者: Wafa Al Shammakh
• 来源期刊: 应用数学与应用物理(英文)
• 学科: 数学
• 关键词: DOMINATION Uphill Domination Uphill Domination Polynomial
• 年，卷（期）: 2020,（6）
• 页码范围: 1168-1179
• 页数: 12页
• 分类号: O15

摘要

A path <i>π</i> = [<i>v</i>₁, <i>v</i>₂, …, <i>v</i>_<em>k</em>] in a graph <i>G</i> = (<i>V</i>, <i>E</i>) is an uphill path if <i>deg</i>(<i>v</i>_<i>i</i>) ≤ <i>deg</i>(<i>v</i>_<i>i</i>+1) for every 1 ≤ <i>i</i> ≤ <i>k</i>. A subset <i>S </i><span style="white-space:nowrap;"><span style="white-space:nowrap;">&#8838;</span></span> <i>V</i>(<i>G</i>) is an uphill dominating set if every vertex <i>v</i>_<i>i</i> <span style="white-space:nowrap;"><span style="white-space:nowrap;">&#8712;</span> </span><i>V</i>(<i>G</i>) lies on an uphill path originating from some vertex in <i>S</i>. The uphill domination number of <i>G</i> is denoted by <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>&#947;</i></span></i></span></i>_<i>up</i>(<i>G</i>) and is the minimum cardinality of the uphill dominating set of <i>G</i>. In this paper, we introduce the uphill domination polynomial of a graph <i>G</i>. The uphill domination polynomial of a graph <i>G</i> of <i>n</i> vertices is the polynomial <img src="Edit_75fb5c37-6ef5-4292-9d3a-4b63343c48ce.bmp" alt="" />, where <em>up</em>(<i>G</i>, <i>i</i>) is the number of uphill dominating sets of size <i>i</i> in <i>G</i>, and <i><span style="white-space:nowrap;"><i><span style="white-space:nowrap;"><i>&#947;</i></span></i></span></i><i>_up</i>(<i>G</i>) is the uphill domination number of <i>G</i>, we compute the uphill domination polynomial and its roots for some families of standard graphs. Also, <i>UP</i>(<i>G</i>, <em>x</em>) for some graph operations is obtained.