Edge adding stability of graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Technical University, Braunschweig, Germany

Abstract

For an arbitrary invariant $\rho(G)$ of a graph $G$ the $\rho$-edge adding stability number $eas_{\rho}(G)$ is the minimum number of edges of the complement $\overline{G}$ whose addition to $G$ results in a graph $H \supseteq G$ with $\rho(H) \neq \rho(G)$. If such an edge set does not exist, then we set $eas_{\rho}(G) = \infty$. In the first part of this paper we give some general results for $eas_{\rho}(G)$. We prove among others a Gallai's theorem type result for invariants that are based on the $\rho$-edge adding stability number.

Keywords

Main Subjects

References

[1] S. Akbari, A. Beikmohammadi, B. Brešar, T. Dravec, M.M. Habibollahi, and N. Movarraei, On the chromatic edge stability index of graphs, European J. Combin. 111 (2023), Article ID: 103690. https://doi.org/10.1016/j.ejc.2023.103690
[2] S. Akbari, A. Beikmohammadi, S. Klavžar, and N. Movarraei, On the chromatic vertex stability number of graphs, European J. Combin. 102 (2022), Article ID: 103504.  https://doi.org/10.1016/j.ejc.2021.103504
[3] S. Akbari, J. Haslegrave, M. Javadi, N. Nahvi, and H. Niaparast, Tight bounds on the chromatic edge stability index of graphs, Discrete Math. 347 (2024), no. 4,  Article ID: 113850.  https://doi.org/10.1016/j.disc.2023.113850
[4] S. Akbari, S. Klavžar, N. Movarraei, and M. Nahvi, Nordhaus–Gaddum and other bounds for the chromatic edge-stability number, European J. Combin. 84 (2020), Article ID: 103042. https://doi.org/10.1016/j.ejc.2019.103042
[5] S. Alikhani and M.R. Piri, On the edge chromatic vertex stability number of graphs, AKCE Int. J. Graphs Comb. 20 (2023), no. 1, 29–34.  https://doi.org/10.1080/09728600.2022.2149367
[6] D. Bauer, F. Harary, J. Nieminen, and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161.  https://doi.org/10.1016/0012-365X(83)90085-7
[7] B. Brešar, S. Klavžar, and N. Movarraei, Critical graphs for the chromatic edge-stability number, Discrete Math. 343 (2020), no. 6, Article ID: 111845.  https://doi.org/10.1016/j.disc.2020.111845
[8] T. Gallai, Über extreme Punkt- und Kantenmengen (German), Ann. Univ. Sci. Budapest. Eótvós Sect. Math. 2 (1959), 133–138.
[9] F. Harary, Changing and unchanging invariants for graphs, Bull. Malaysian Math. Soc. 5 (1982), 73–78.
[10] T.W. Haynes, L.M. Lawson, R.C. Brigham, and R.D. Dutton, Changing and unchanging of the graphical invariants: minimum and maximum degree, maximum clique size, node independence number and edge independence number, Congr. Numer. 72 (1990), 239–252.
[11] A. Kemnitz and M. Marangio, On the $rho$-subdivision number of graphs., Discuss. Math. Graph Theory 43 (2023), no. 4, 979–997.  https://doi.org/10.7151/dmgt.2412
[12] A. Kemnitz and M. Marangio, On the $rho$-edge stability number of graphs, Discuss. Math. Graph Theory 42 (2022), no. 1, 249–262.  https://doi.org/10.7151/dmgt.2255
[13] A. Kemnitz and M. Marangio, On the total chromatic edge stability number and the total chromatic subdivision number of graphs, Discrete Math. Lett 10 (2022), 1–8.  https://doi.org/10.47443/dml.2021.111
[14] A. Kemnitz and M. Marangio, A Gallai’s theorem type result for the edge stability of graphs, Discrete Math. Lett. 12 (2023), 118–121.  https://doi.org/10.47443/dml.2023.088
[15] A. Kemnitz and M. Marangio, On the vertex stability number of graphs, Discrete Appl. Math. 344 (2024), 1–9.
https://doi.org/10.1016/j.dam.2023.11.008
[16] 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
[17] W. Staton, Edge deletions and the chromatic number, Ars Combin. 10 (1980), 103–106.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 02 July 2025

Files

Share

How to cite

Statistics