DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

A. Kemnitz

Arnfried Kemnitz

Computational Mathematics
Technical University Braunschweig

email: a.kemnitz@tu-bs.de

0000-0002-6959-1051

M. Marangio

Massimiliano Marangio

.

email: m.marangio@tu-bs.de

0000-0002-5285-5866

Title:

On the $\rho$-edge stability number of graphs

PDF

Source:

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:

  1. S. Arumugam, I. Sahul Hamid and A. Muthukamatchi, Independent domination and graph colorings, Ramanujan Math. Soc. Lect. Notes Ser. 7 (2008) 195–203.
  2. 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
  3. 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
  4. 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
  5. W. Staton, Edge deletions and the chromatic number, Ars Combin. 10 (1980) 103–106.
  6. 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