There are Finitely Many Uniformly Most Reliable Graphs of Corank 5
摘要
If G is a simple graph and \(\rho \in [0,1]\) , the reliability \(R_G(\rho )\) is the probability of G being connected after each of its edges is removed independently with probability \(\rho \) . A simple graph G is a uniformly most reliable graph (UMRG) if \(R_G(\rho )\ge R_H(\rho )\) for every \(\rho \in [0,1]\) and every simple graph H on the same number of vertices and edges as G. Boesch conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch’s conjecture appeared in the literature. It is known that Boesch’s conjecture holds whenever the corank, defined as \(c=m-n+1\) , is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch’s conjecture holds whenever the corank c is between 5 and 8, provided that the number of vertices is at least \(2c-2\) . It is known that for each positive integer s there is no uniformly most reliable graph of corank 5 and \(12s+4\) vertices. Here it is proved that there are only finitely many uniformly most reliable graphs of corank 5. This is in strong contrast with classes of graphs whose corank is not greater than 4 for which uniformly most reliable graphs always exist.