Changing and unchanging of the domination number of a graph: path addition numbers
Discussiones Mathematicae Graph Theory
Received 15.01.2018, Revised 02.11.2018, Accepted 03.11.2018, doi: 10.7151/dmgt.2189
Given a graph G = (V,E) and two its distinct vertices u and v, the (u,v)-Pk- addition graph of G is the graph Gu,v,k-2 obtained from disjoint union of G and a path Pk: x0,x1,...,xk-1, k ≥ 2, by identifying the vertices u and x0, and identifying the vertices v and xk-1. We prove that γ(G)-1 ≤ γ(Gu,v,k) for all k ≥ 1, and γ(Gu,v,k)>γ(G) when k ≥ 5. We also provide necessary and sufficient conditions for the equality γ(Gu,v,k)=γ(G) to be valid for each pair u,v ∈V(G). In addition, we establish sharp upper and lower bounds for the minimum, respectively maximum, k in a graph G over all pairs of vertices u and v in G such that the (u, v)-Pk-addition graph of G has a larger domination number than G, which we consider separately for adjacent and non-adjacent pairs of vertices.
domination number, path addition