Geodesic
Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 365-379.

Voir la notice de l'article provenant de la source Library of Science

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) gt;γ(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 
@article{DMGT_2021_41_2_a1,
     author = {Samodivkin, Vladimir},
     title = {Changing and {Unchanging} of the {Domination} {Number} of a {Graph:} {Path} {Addition} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {365--379},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a1/}
}
TY  - JOUR
AU  - Samodivkin, Vladimir
TI  - Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 365
EP  - 379
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a1/
LA  - en
ID  - DMGT_2021_41_2_a1
ER  - 
%0 Journal Article
%A Samodivkin, Vladimir
%T Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 365-379
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a1/
%G en
%F DMGT_2021_41_2_a1
Samodivkin, Vladimir. Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 365-379. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a1/

[1] N. Ananchuen, W. Ananchuen and R.E.L. Aldred, Maximal 3-gamma-vertex-critical graphs, Util. Math. 88 (2012) 75–90.

[2] A. Bhattacharya and G.R. Vijayakumar, Effect of edge-subdivision on vertex-domination in a graph, Discuss. Math. Graph Theory 22 (2002) 335–347. doi:10.7151/dmgt.1179

[3] R.C. Brigham, P.Z. Chinn and R.D. Dutton, A Study of Vertex Domination Critical Graphs (Technical Report, University of Central Florida, 1984).

[4] R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173–179. doi:10.1002/net.3230180304

[5] G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and R.C. Laskar, Excellent trees, Bull. Inst. Combin. Appl. 34 (2002) 27–38.

[6] B. Hartnell and D. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173–177. doi:10.1016/0012-365X(94)90111-2

[7] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854. doi:10.1016/j.disc.2012.11.031

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker Inc., New York, 1998).

[9] T.W. Haynes, M.A. Henning and P.J. Slater, Strong equality of domination parameters in trees, Discrete Math. 260 (2003) 77–87. doi:10.1016/S0012-365X(02)00451-X

[10] V. Samodivkin, Common extremal graphs for three inequalities involving domination parameters, Trans.Comb. 6 (2017) 1–9. doi:10.22108/TOC.2017.21464

[11] H.B. Walikar and B.D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett. 2 (1979) 70–72.