Edge fault-tolerance of strongly Menger edge connected graphs (Q2666578)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge fault-tolerance of strongly Menger edge connected graphs |
scientific article |
Statements
Edge fault-tolerance of strongly Menger edge connected graphs (English)
0 references
23 November 2021
0 references
A connected graph \(G\) is said to be strongly Menger edge connected (\(SM\)-\(\lambda\) for short) if any two of its vertices \(x\), \(y\) are connected by min\(\{d(x),d(y)\}\) edge-disjoint paths, where \(d(x)\) is the degree of \(x\). The maximum edge-fault-tolerant with respect to the \(SM\)-\(\lambda\) property of \(G\), denoted by \(sm_{\lambda}(G)\), is the maximum integer \(m\) such that \(G - F\) is still \(SM\)-\(\lambda\) for any edge-set \(F\) with \(|F | \leq m\). In this paper, the author gives a sharp lower and upper bound for \(sm_{\lambda}(G)\), and a characterization of the minimum upper bound. Furthermore, for \(k\)-regular graphs, some examples are proposed to show that \(sm_{\lambda}(G)\) can reach every value between the lower bound and the upper bound when \(k\) is odd or even, and the only possible odd value is \(k - 1\) if \(k\) is even. Moreover, the exact value of \(sm_{\lambda}(G)\) when \(G\) is a vertex-transitive, edge-transitive, or optimal regular graph was completely determined.
0 references
fault-tolerance
0 references
strongly Menger edge-connected graph
0 references
vertex-transitive graph
0 references
edge-transitive graph
0 references
0 references
0 references
0 references
0 references
0 references
0 references