Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
dominating set; edge subdivision; domination multisubdivision number; hereditary graph property
dominating set; edge subdivision; domination multisubdivision number; hereditary graph property
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$.
References:
[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 10.7151/dmgt.1798 | MR 3338756 | Zbl 1311.05143
[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 10.7151/dmgt.1037 | MR 1633268 | Zbl 0902.05026
[3] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. DOI 10.1002/net.3230100304 | MR 0584887 | Zbl 0447.05039
[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 10.1016/S0012-365X(03)00302-9 | MR 2046628 | Zbl 1031.05093
[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 0357174 | Zbl 0305.05114
[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 2462631 | Zbl 1161.05055
[8] Favaron, O., Karami, H., Sheikholeslami, S. M.: Paired-domination subdivision numbers of graphs. Graphs Comb. 25 (2009), 503-512. DOI 10.1007/s00373-005-0871-1 | MR 2575597 | Zbl 1216.05102
[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 0812672 | Zbl 0573.05050
[10] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math., Graph Theory 24 (2004), 239-248. DOI 10.7151/dmgt.1228 | MR 2120566 | Zbl 1065.05069
[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
[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 1772765 | Zbl 0959.05084
[13] Grobler, P. J. P., Mynhardt, C. M.: Domination parameters and edge-removal-critical graphs. Discrete Math. 231 (2001), 221-239. DOI 10.1016/S0012-365X(00)00319-8 | MR 1821961 | Zbl 0973.05056
[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 1605684 | Zbl 0890.05002
[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 10.7151/dmgt.1244 | MR 2120069 | Zbl 1065.05070
[16] Haynes, T. W., Slater, P. J.: Paired-domination in graphs. Networks 32 (1998), 199-206. DOI 10.1002/(SICI)1097-0037(199810)32:3 | MR 1645415 | Zbl 0997.05074
[17] Hedetniemi, S. M., Hedetniemi, S. T., Rall, D. F.: Acyclic domination. Discrete Math. 222 (2000), 151-165. DOI 10.1016/S0012-365X(00)00012-1 | MR 1771395 | Zbl 0961.05052
[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
[19] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141-146. DOI 10.1016/j.disc.2003.11.054 | MR 2084289 | Zbl 1051.05069
[20] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. MR 2428312 | Zbl 1199.05269
[21] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. MR 2554536 | Zbl 1207.05145
[22] Samodivkin, V.: Domination with respect to nondegenerate properties: vertex and edge removal. Math. Bohem. 138 (2013), 75-85. MR 3076222 | Zbl 1274.05363
[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 10.1007/s10587-013-0013-5 | MR 3035506 | Zbl 1274.05364
[24] Sampathkumar, E., Walikar, H. B.: The connected domination of a graph. J. Math. Phys. Sci. 13 (1979), 607-613. MR 0575817 | Zbl 0449.05057
[25] Velammal, S.: Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University (1997).
Search
Partner of
