Geodesic
Changing of the domination number of a graph: edge multisubdivision and edge removal
Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 9-20
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

For a graphical property $\mathcal {P}$ and a graph $G$, a subset $S$ of vertices of $G$ is a $\mathcal {P}$-set if the subgraph induced by $S$ has the property $\mathcal {P}$. The domination number with respect to the property $\mathcal {P}$, denoted by $\gamma _{\mathcal {P}} (G)$, is the minimum cardinality of a dominating $\mathcal {P}$-set. We define the domination multisubdivision number with respect to $\mathcal {P}$, denoted by ${\rm msd} _{\mathcal {P}}(G)$, as a minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to change $\gamma _{\mathcal {P}} (G)$. In this paper \item {(a)} we present necessary and sufficient conditions for a change of $\gamma _{\mathcal {P}}(G)$ after subdividing an edge of $G$ once, \item {(b)} we prove that if $e$ is an edge of a graph $G$ then $\gamma _{\mathcal {P}} (G_{e,1}) \gamma _{\mathcal {P}} (G)$ if and only if $\gamma _{\mathcal {P}} (G-e) \gamma _{\mathcal {P}} (G)$ ($G_{e,t}$ denotes the graph obtained from $G$ by subdivision of $e$ with $t$ vertices), \item {(c)} we also prove that for every edge of a graph $G$ we have $\gamma _{\mathcal {P}}(G-e)\leq \gamma _{\mathcal {P}}(G_{e,3})\leq \gamma _{\mathcal {P}}(G-e) + 1$, and \item {(d)} we show that ${\rm msd}_{\mathcal {P}}(G) \leq 3$, where $\mathcal {P}$ is hereditary and closed under union with $K_1$.
For a graphical property $\mathcal {P}$ and a graph $G$, a subset $S$ of vertices of $G$ is a $\mathcal {P}$-set if the subgraph induced by $S$ has the property $\mathcal {P}$. The domination number with respect to the property $\mathcal {P}$, denoted by $\gamma _{\mathcal {P}} (G)$, is the minimum cardinality of a dominating $\mathcal {P}$-set. We define the domination multisubdivision number with respect to $\mathcal {P}$, denoted by ${\rm msd} _{\mathcal {P}}(G)$, as a minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to change $\gamma _{\mathcal {P}} (G)$. In this paper \item {(a)} we present necessary and sufficient conditions for a change of $\gamma _{\mathcal {P}}(G)$ after subdividing an edge of $G$ once, \item {(b)} we prove that if $e$ is an edge of a graph $G$ then $\gamma _{\mathcal {P}} (G_{e,1}) \gamma _{\mathcal {P}} (G)$ if and only if $\gamma _{\mathcal {P}} (G-e) \gamma _{\mathcal {P}} (G)$ ($G_{e,t}$ denotes the graph obtained from $G$ by subdivision of $e$ with $t$ vertices), \item {(c)} we also prove that for every edge of a graph $G$ we have $\gamma _{\mathcal {P}}(G-e)\leq \gamma _{\mathcal {P}}(G_{e,3})\leq \gamma _{\mathcal {P}}(G-e) + 1$, and \item {(d)} we show that ${\rm msd}_{\mathcal {P}}(G) \leq 3$, where $\mathcal {P}$ is hereditary and closed under union with $K_1$.
DOI : 10.21136/MB.2017.0009-15
Classification : 05C69
Keywords: dominating set; edge subdivision; domination multisubdivision number; hereditary graph property 
@article{10_21136_MB_2017_0009_15,
     author = {Samodivkin, Vladimir},
     title = {Changing of the domination number of a graph: edge multisubdivision and edge removal},
     journal = {Mathematica Bohemica},
     pages = {9--20},
     year = {2017},
     volume = {142},
     number = {1},
     doi = {10.21136/MB.2017.0009-15},
     mrnumber = {3619983},
     zbl = {06738566},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0009-15/}
}
TY  - JOUR
AU  - Samodivkin, Vladimir
TI  - Changing of the domination number of a graph: edge multisubdivision and edge removal
JO  - Mathematica Bohemica
PY  - 2017
SP  - 9
EP  - 20
VL  - 142
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0009-15/
DO  - 10.21136/MB.2017.0009-15
LA  - en
ID  - 10_21136_MB_2017_0009_15
ER  - 
%0 Journal Article
%A Samodivkin, Vladimir
%T Changing of the domination number of a graph: edge multisubdivision and edge removal
%J Mathematica Bohemica
%D 2017
%P 9-20
%V 142
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2017.0009-15/
%R 10.21136/MB.2017.0009-15
%G en
%F 10_21136_MB_2017_0009_15
Samodivkin, Vladimir. Changing of the domination number of a graph: edge multisubdivision and edge removal. Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 9-20. doi: 10.21136/MB.2017.0009-15

[1] Avella-Alaminos, D., Dettlaff, M., Lemańska, M., Zuazua, R.: Total domination multisubdivision number of a graph. Discuss. Math. Graph Theory 35 (2015), 315-327. | DOI | MR | JFM

[2] Borowiecki, M., Broere, I., Frick, M., Mihók, P., Semanišin, G.: A survey of hereditary properties of graphs. Discuss. Math., Graph Theory 17 (1997), 5-50. | DOI | MR | JFM

[3] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. | DOI | MR | JFM

[4] Cockayne, E. J., Favaron, O., Mynhardt, C. M.: On $i^-$-ER-critical graphs. 6th Int. Conf. Graph Theory. Discrete Math. 276 (2004), 111-125. | DOI | MR | JFM

[5] Cockayne, E. J., Hedetniemi, S. T.: Independence graphs. Proc. 5th Southeast. Conf. Comb., Graph Theor., Comput., Boca Raton 1974 Utilitas Math., Winnipeg, Man. (1974), 471-491. | MR | JFM

[6] Dettlaff, M., Raczek, J., Topp, J.: Domination subdivision and domination multisubdivision numbers of graphs. Available at http://arxiv.org/pdf/1310.1345v2.pdf

[7] Favaron, O., Karami, H., Sheikholeslami, S. M.: Connected domination subdivision numbers of graphs. Util. Math. 77 (2008), 101-111. | MR | JFM

[8] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs. Graphs Comb. 25 (2009), 503-512. | DOI | MR | JFM

[9] Fink, J. F., Jacobson, M. S.: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science. Proc. 5th Int. Conf., Kalamazoo/Mich. 1984 John Wiley, New York (1985), 301-311 Y. Alavi et al. | MR | JFM

[10] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math., Graph Theory 24 (2004), 239-248. | DOI | MR | JFM

[11] Grobler, P. J. P.: Critical Concepts in Domination, Independence and Irredundance of Graphs. Ph.D. Thesis, University of South Africa, ProQuest LLC (1999). | MR

[12] Grobler, P. J. P., Mynhardt, C. M.: Upper domination parameters and edge-critical graphs. J. Comb. Math. Comb. Comput. 33 (2000), 239-251. | MR | JFM

[13] Grobler, P. J. P., Mynhardt, C. M.: Domination parameters and edge-removal-critical graphs. Discrete Math. 231 (2001), 221-239. | DOI | MR | JFM

[14] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Pure and Applied Mathematics 208 Marcel Dekker, New York (1998). | MR | JFM

[15] Haynes, T. W., Henning, M. A., Hopkins, L. S.: Total domination subdivision numbers of graphs. Discuss. Math., Graph Theory 24 (2004), 457-467. | DOI | MR | JFM

[16] Haynes, T. W., Slater, P. J.: Paired-domination in graphs. Networks 32 (1998), 199-206. | DOI | MR | JFM

[17] Hedetniemi, S. M., Hedetniemi, S. T., Rall, D. F.: Acyclic domination. Discrete Math. 222 (2000), 151-165. | DOI | MR | JFM

[18] Lemańska, M., Tey, J., Zuazua, R.: Relations between edge removing and edge subdivision concerning domination number of a graph. Available at | arXiv

[19] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141-146. | DOI | MR | JFM

[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. | MR | JFM

[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. | MR | JFM

[22] Samodivkin, V.: Domination with respect to nondegenerate properties: vertex and edge removal. Math. Bohem. 138 (2013), 75-85. | MR | JFM

[23] Samodivkin, V.: Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces. Czech. Math. J. 63 (2013), 191-204. | DOI | MR | JFM

[24] Sampathkumar, E., Walikar, H. B.: The connected domination of a graph. J. Math. Phys. Sci. 13 (1979), 607-613. | MR | JFM

[25] Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University (1997).

Cité par Sources :