Article in volume
Authors:
Title:
On the $\rho$-edge stability number of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 249-262
Received: 2019-06-13 , Revised: 2019-09-26 , Accepted: 2019-09-26 , Available online: 2019-11-12 , https://doi.org/10.7151/dmgt.2255
Abstract:
For an arbitrary invariant $\rho(G)$ of a graph $G$ the $\rho$-edge stability
number $\mathit{es}_{\rho}(G)$ is the minimum number of edges of $G$ whose removal
results in a graph $H \subseteq G$ with $\rho(H) \neq \rho(G)$ or with
$E(H) = \emptyset$.
In the first part of this paper we give some general lower and upper bounds for
the $\rho$-edge stability number. In the second part we study the $\chi'$-edge
stability number of graphs, where $\chi' = \chi'(G)$ is the chromatic index of
$G$. We prove some general results for the so-called chromatic edge stability
index $\mathit{es}_{\chi'}(G)$ and determine $\mathit{es}_{\chi'}(G)$ exactly for specific classes of graphs.
Keywords:
edge stability number, line stability, invariant, chromatic edge stability index, chromatic index, edge coloring
References:
- S. Arumugam, I. Sahul Hamid and A. Muthukamatchi, Independent domination and graph colorings, Ramanujan Math. Soc. Lect. Notes Ser. 7 (2008) 195–203.
- 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 - 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 - M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981) 45–53.
https://doi.org/10.1002/jgt.3190050103 - W. Staton, Edge deletions and the chromatic number, Ars Combin. 10 (1980) 103–106.
- J.-M. Xu, On bondage numbers of graphs: A survey with some comments, Int. J. Comb. 2013 (2013) ID 595210.
https://doi.org/10.1155/2013/595210
Close