Mathematics (Feb 2021)

On the Paired-Domination Subdivision Number of a Graph

  • Guoliang Hao,
  • Seyed Mahmoud Sheikholeslami,
  • Mustapha Chellali,
  • Rana Khoeilar,
  • Hossein Karami

DOI
https://doi.org/10.3390/math9040439
Journal volume & issue
Vol. 9, no. 4
p. 439

Abstract

Read online

In order to increase the paired-domination number of a graph G, the minimum number of edges that must be subdivided (where each edge in G can be subdivided no more than once) is called the paired-domination subdivision number sdγpr(G) of G. It is well known that sdγpr(G+e) can be smaller or larger than sdγpr(G) for some edge e∉E(G). In this note, we show that, if G is an isolated-free graph different from mK2, then, for every edge e∉E(G), sdγpr(G+e)≤sdγpr(G)+2Δ(G).

Keywords