English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

If $G$ is a simple graph and $\rho\in[0,1]$, the reliability $R_G(\rho)$ isthe probability of $G$ being connected after each of its edges is removedindependently with probability $\rho$. A simple graph $G$ is a \emph{uniformlymost reliable graph} (UMRG) if $R_G(\rho)\geq R_H(\rho)$ for every$\rho\in[0,1]$ and every simple graph $H$ on the same number of vertices andedges as $G$. Boesch [J.\ Graph Theory 10 (1986), 339--352] 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 ofvertices and edges. Some counterexamples to Boesch's conjecture were given byKelmans, Myrvold et al., and Brown and Cox. It is known that Boesch'sconjecture holds whenever the corank, defined as $c=m-n+1$, is at most $4$ (andthe corresponding UMRGs are fully characterized). Ath and Sobel conjecturedthat Boesch's conjecture holds whenever the corank $c$ is between $5$ and $8$,provided the number of vertices is at least $2c-2$. In this work, we give aninfinite family of counterexamples to Boesch's conjecture of corank $5$. Theseare the first reported counterexamples that attain the minimum possible corank.As a byproduct, the conjecture by Ath and Sobel is disproved.

Nonexistence of uniformly most reliable graphs of least corank