| Title:
|
Changing of the domination number of a graph: edge multisubdivision and edge removal (English) |
| Author:
|
Samodivkin, Vladimir |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
142 |
| Issue:
|
1 |
| Year:
|
2017 |
| Pages:
|
9-20 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
dominating set |
| Keyword:
|
edge subdivision |
| Keyword:
|
domination multisubdivision number |
| Keyword:
|
hereditary graph property |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 06738566 |
| idMR:
|
MR3619983 |
| DOI:
|
10.21136/MB.2017.0009-15 |
| . |
| Date available:
|
2017-02-21T17:19:54Z |
| Last updated:
|
2020-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146005 |
| . |
| Reference:
|
[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. Zbl 1311.05143, MR 3338756, 10.7151/dmgt.1798 |
| Reference:
|
[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. Zbl 0902.05026, MR 1633268, 10.7151/dmgt.1037 |
| Reference:
|
[3] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs.Networks 10 (1980), 211-219. Zbl 0447.05039, MR 0584887, 10.1002/net.3230100304 |
| Reference:
|
[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. Zbl 1031.05093, MR 2046628, 10.1016/S0012-365X(03)00302-9 |
| Reference:
|
[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. Zbl 0305.05114, MR 0357174 |
| Reference:
|
[6] Dettlaff, M., Raczek, J., Topp, J.: Domination subdivision and domination multisubdivision numbers of graphs.Available at http://arxiv.org/pdf/1310.1345v2.pdf. |
| Reference:
|
[7] Favaron, O., Karami, H., Sheikholeslami, S. M.: Connected domination subdivision numbers of graphs.Util. Math. 77 (2008), 101-111. Zbl 1161.05055, MR 2462631 |
| Reference:
|
[8] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs.Graphs Comb. 25 (2009), 503-512. Zbl 1216.05102, MR 2575597, 10.1007/s00373-005-0871-1 |
| Reference:
|
[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. Zbl 0573.05050, MR 0812672 |
| Reference:
|
[10] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters.Discuss. Math., Graph Theory 24 (2004), 239-248. Zbl 1065.05069, MR 2120566, 10.7151/dmgt.1228 |
| Reference:
|
[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 2716892 |
| Reference:
|
[12] Grobler, P. J. P., Mynhardt, C. M.: Upper domination parameters and edge-critical graphs.J. Comb. Math. Comb. Comput. 33 (2000), 239-251. Zbl 0959.05084, MR 1772765 |
| Reference:
|
[13] Grobler, P. J. P., Mynhardt, C. M.: Domination parameters and edge-removal-critical graphs.Discrete Math. 231 (2001), 221-239. Zbl 0973.05056, MR 1821961, 10.1016/S0012-365X(00)00319-8 |
| Reference:
|
[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). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[15] Haynes, T. W., Henning, M. A., Hopkins, L. S.: Total domination subdivision numbers of graphs.Discuss. Math., Graph Theory 24 (2004), 457-467. Zbl 1065.05070, MR 2120069, 10.7151/dmgt.1244 |
| Reference:
|
[16] Haynes, T. W., Slater, P. J.: Paired-domination in graphs.Networks 32 (1998), 199-206. Zbl 0997.05074, MR 1645415, 10.1002/(SICI)1097-0037(199810)32:3 |
| Reference:
|
[17] Hedetniemi, S. M., Hedetniemi, S. T., Rall, D. F.: Acyclic domination.Discrete Math. 222 (2000), 151-165. Zbl 0961.05052, MR 1771395, 10.1016/S0012-365X(00)00012-1 |
| Reference:
|
[18] Lemańska, M., Tey, J., Zuazua, R.: Relations between edge removing and edge subdivision concerning domination number of a graph.Available at http://arxiv.org/abs/1409.7508. |
| Reference:
|
[19] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties.Discrete Math. 286 (2004), 141-146. Zbl 1051.05069, MR 2084289, 10.1016/j.disc.2003.11.054 |
| Reference:
|
[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties.Math. Bohem. 133 (2008), 167-178. Zbl 1199.05269, MR 2428312 |
| Reference:
|
[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number.Australas. J. Comb. 45 (2009), 217-226. Zbl 1207.05145, MR 2554536 |
| Reference:
|
[22] Samodivkin, V.: Domination with respect to nondegenerate properties: vertex and edge removal.Math. Bohem. 138 (2013), 75-85. Zbl 1274.05363, MR 3076222 |
| Reference:
|
[23] Samodivkin, V.: Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.Czech. Math. J. 63 (2013), 191-204. Zbl 1274.05364, MR 3035506, 10.1007/s10587-013-0013-5 |
| Reference:
|
[24] Sampathkumar, E., Walikar, H. B.: The connected domination of a graph.J. Math. Phys. Sci. 13 (1979), 607-613. Zbl 0449.05057, MR 0575817 |
| Reference:
|
[25] Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics.Ph.D. Thesis, Manonmaniam Sundaranar University (1997). |
| . |
