Article in volume
Authors:
Arnfried Kemnitz
Computational Mathematics
Technical University Braunschweig
email: a.kemnitz@tu-bs.de
Title:
On the $\rho$-subdivision number of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 979-997
Received: 2020-08-14 , Revised: 2021-05-19 , Accepted: 2021-05-20 , Available online: 2021-06-24 , https://doi.org/10.7151/dmgt.2412
Abstract:
For an arbitrary invariant $\rho(G)$ of a graph $G$ the $\rho$-subdivision
number $sd_{\rho}(G)$ is the minimum number of edges of $G$ whose subdivision results
in a graph $H$ with $\rho(H) \neq \rho(G)$. Set $sd_{\rho}(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
$\rho$-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 $\rho$-edge
stability number for these three invariants. In the last part we consider a
modification, namely the $\rho$-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
References:
- S. Arumugam, (2019), private communication.
- G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, 2009).
- 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 - 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 - 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 - 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 - 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 - S. Velammal, Studies in Graph Theory: Covering, Independence, Domination and Related Topics, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997).
- 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
Close