DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

A. Kemnitz, M. Marangio

Title:

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

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-06-13, Revised: 2019-09-26, Accepted: 2019-09-26, https://doi.org/10.7151/dmgt.2255

Abstract:

For an arbitrary invariant $\rho(G)$ of a graph $G$ the $\rho$-edge stability number $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$.<br>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 $es_{\lambda'}(G)$ and determine $es_{\lambda'}(G)$ exactly for specific classes of graphs.

Keywords:

edge stability number, line stability, invariant, chromatic edge stability index, chromatic index, edge coloring

PDF
Close