Conditional edge connectivity properties, reliability comparisons and transitivity of graphs

DOI10.1016/S0012-365X(02)00299-6MaRDI QIDQ1850060zbMATH OpenOpenAlexFDO

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00299-6

conditional edge-connectivity edge-transitive girth locally most reliable unreliability polynomial vertex-transitive

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Review text

For a simple undirected finite graph \(G\) and for each nonnegative integer \(i\), let \(\lambda_{i}\) denote the size of a smallest separating set \(S\subset E(G)\) such that every component of \(G-S\) contains at least \(i+1\) vertices. Suppose that \(G\) is a connected \(d\)-valent graph (\(d\geq 4\)) on at least 6 vertices. If \(G\) is either (i) edge-transitive with girth \(g\geq 4\) or (ii) vertex-transitive with girth \(g\geq 5\), then \(\lambda_{i}=(i+1)d-2i\) for \(0\leq i\leq\min\{g-2,n/2-1\}\). Suppose that the edges of \(G\) fail independently with probability \(\rho\in(0,1)\), and let \(P(G,\rho)\) denote the polynomial (in \(\rho\)) that measures the probability of \(G\) being not connected. Call \(G\) locally most reliable (LMR) if \(P(G,\rho)\leq P(G',\rho)\) for all graphs \(G'\) having the same numbers of vertices and edges as \(G\) and all sufficiently small values of \(\rho\). It is shown that for \(a\geq 5\) the complete bipartite graph \(K_{a+1,a+1}\) minus a 1-factor is the only LMR graph on \(2(a+1)\) vertices and \(a(a+1)\) edges.

Cited in

(67)

This page was built for publication: Conditional edge connectivity properties, reliability comparisons and transitivity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850060)