论文标题
反示例Boesch的猜想
Counterexample to a Boesch's Conjecture
论文作者
论文摘要
网络可靠性分析中的关键问题。具有$ n $节点且其$ e $边缘与概率$ p $独立失败的图形是\ emph {均匀可靠的图形}（umrg），如果在所有图表中具有最高的可靠性，该图表的所有订单和尺寸的每个值的每个值都相同。 \ emph {全终端可靠性}是$ p $中的多项式，如果其某些组件失败，则定义了网络的概率保持连接。如果可靠性多项式的系数通过图最大化，则该图称为\ textIt {stront均匀最可靠的图}（sumrg），并且应为umrg。最多可以对带顶点的SUMRG进行详尽的计算机搜索。提出了最大化树号的10至14个顶点的常规图形，作为候选umrg的候选。作为出色的结果，发现有9个顶点和18个边缘的UMRG，发现了Girth 3，比Boesch在1986年的猜想小。 $ n = 3k+r $，$ n \ geq5 $和$ e = {n（n-3）}/{2} $。提出了对Boesch的猜想的重新制定，表明，如果存在$（n，{kn}/{2}）$ - umrg存在，并且它具有Girth $ g $，那么它在所有$ k $ regular $（n，{kn}/{kn}/{2}）中都有最大的girth，n，{kn}/{2} $（n，{kn}/{2}）$ gragrs thing the girth $ g $。
A key issue in network reliability analysis. A graph with $n$ nodes and whose $e$ edges fail independently with probability $p$ is an \emph{Uniformly Most Reliable Graph} (UMRG) if it has the highest reliability among all graphs with the same order and size for every value of $p$. The \emph{all-terminal reliability} is a polynomial in $p$ which defines the probability of a network to remain connected if some of its components fail. If the coefficients of the reliability polynomial are maximized by a graph, that graph is called \textit{Strong Uniformly Most Reliable Graph} (SUMRG) and it should be UMRG. An exhaustive computer search of the SUMRG with vertices up to 9 is done. Regular graphs with 10 to 14 vertices that maximize tree number are proposed as candidates to UMRG. As an outstanding result a UMRG with 9 vertices and 18 edges which has girth 3 is found, so smaller than the conjectured by Boesch in 1986. A new conjecture about UMRG's topology is posed here: the $(n,e)$-UMRG is $\overline{(k-1)C_3\cup C_{3+r}}$ whenever $n=3k+r$,$n\geq5$ and $e={n(n-3)}/{2}$. A reformulation of Boesch's conjecture is presented stating that if a $(n, {kn}/{2})$-UMRG exists and it has girth $g$, then it has maximum girth among all $k$-regular $(n,{kn}/{2})$ graphs and minimum number of $g$-cycles among those $k$-regular $(n,{kn}/{2})$ graphs with girth $g$.
