1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On the ρ-Subdivision Number of Graphs

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Aug 2020
Accepted: 20 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 agraph 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

MSC 2010

[1] S. Arumugam (2019), private communication.Search in Google Scholar

[2] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC, Boca Raton, 2009).10.1201/9781584888017Search in Google Scholar

[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.57510.7494/OpMath.2016.36.5.575Search in Google Scholar

[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.112610.7151/dmgt.1126Search in Google Scholar

[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-y10.1007/s00373-018-1972-ySearch in Google Scholar

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

[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.04810.1016/j.disc.2005.11.048Search in Google Scholar

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

[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/16080623410.21817/ijet/2016/v8i6/160806234Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo