Authors: V. Samodivkin Title: Changing and unchanging of the domination number of a graph: path addition numbers Source: Discussiones Mathematicae Graph Theory Received 15.01.2018, Revised 02.11.2018, Accepted 03.11.2018, doi: 10.7151/dmgt.2189 | |
Abstract: Given a graph G = (V,E) and two its distinct vertices u and v, the (u,v)-P_{k}- addition graph of G is the graph G_{u,v,k-2} obtained from disjoint union of G and a path P_{k}: x_{0},x_{1},...,x_{k-1}, k ≥ 2, by identifying the vertices u and x_{0}, and identifying the vertices v and x_{k-1}. We prove that γ(G)-1 ≤ γ(G_{u,v,k}) for all k ≥ 1, and γ(G_{u,v,k})>γ(G) when k ≥ 5. We also provide necessary and sufficient conditions for the equality γ(G_{u,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)-P_{k}-addition graph of G has a larger domination number than G, which we consider separately for adjacent and non-adjacent pairs of vertices. | |
Keywords: domination number, path addition | |
Links: |