Geodesic
On the $\rho$-subdivision number of graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 979-997 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For an arbitrary invariant ρ(G) of a graph G the ρ-subdivision number sd_ρ(G) is the minimum number of edges of G whose subdivision results in a graph H with ρ(H) ρ(G). Set sd_ρ(G) = |E(G)| if such an edge set does not exist. In the first part of this paper we give some general results for the ρ-subdivision number. In the second part we study this parameter for the chromatic number, for the chromatic index, and for the total chromatic number. We show among others that there is a strong relationship to the ρ-edge stability number for these three invariants. In the last part we consider a modification, namely the ρ-multiple subdivision number where we allow multiple subdivisions of the same edge.
Keywords: subdivision number, edge stability number, edge subdivision, chromatic number, chromatic index, total chromatic number 
@article{DMGT_2023_43_4_a6,
     author = {Kemnitz, Arnfried and Marangio, Massimiliano},
     title = {On the $\rho$-subdivision number of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {979--997},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/}
}
TY  - JOUR
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
TI  - On the $\rho$-subdivision number of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 979
EP  - 997
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/
LA  - en
ID  - DMGT_2023_43_4_a6
ER  - 
%0 Journal Article
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%T On the $\rho$-subdivision number of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 979-997
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/
%G en
%F DMGT_2023_43_4_a6
Kemnitz, Arnfried; Marangio, Massimiliano. On the $\rho$-subdivision number of graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 979-997. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a6/

[1] S. Arumugam, (2019), private communication.

[2] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, 2009).

[3] M. Dettlaff, J. Raczek and I.G. Yero, Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs, Opuscula Math. 36 (2016) 575–588. https://doi.org/10.7494/OpMath.2016.36.5.575

[4] T.W. Haynes, S.M. Hedetniemi and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000) 271–280. https://doi.org/10.7151/dmgt.1126

[5] A. Kemnitz, M. Marangio and N. Movarraei, On the chromatic edge stability number of graphs, Graphs Combin. 34 (2018) 1539–1551. https://doi.org/10.1007/s00373-018-1972-y

[6] A. Kemnitz and M. Marangio, On the \rho-edge stability number of graphs, Discuss. Math. Graph Theory (2019), in press. https://doi.org/10.7151/dmgt.2255

[7] P. Mihók and G. Semanišin, On invariants of hereditary graph properties, Discrete Math. 307 (2007) 958–963. https://doi.org/10.1016/j.disc.2005.11.048

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

[9] M. Yamuna and K. Karthika, A survey on the effect of graph operations on the domination number of a graph, Internat. J. Engineering and Technology 8 (Dec 2016–Jan 2017) 2749–2771. https://doi.org/10.21817/ijet/2016/v8i6/160806234