2024/10/01 by Nathan Kahl, Kahl, Nathan, Kristi Luttrell +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2410.01120
openalex publication_date 2024/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Boesch, Li, and Suffel were the first to identify the existence of uniformly optimally reliable graphs (UOR graphs), graphs which maximize all-terminal reliability over all graphs with n vertices and m edges. The all-terminal reliability of a graph, and more generally a graph's all-terminal reliability polynomial R(G;p), may both be obtained via the Tutte polynomial T(G;x,y) of the graph G. Here we show that the UOR graphs found earlier are in fact maximum graphs for the Tutte polynomial itself, in the sense that they are maximum not just for all-terminal reliability but for a vast array of other parameters and polynomials that may be obtained from T(G;x,y) as well. These parameters include, but are not limited to, enumerations of a wide variety of well-known orientations, partial orientations, and fourientations of G; the magnitudes of the coefficients of the chromatic and flow polynomials of G; and a wide variety of generating functions, such as generating functions enumerating spanning forests and spanning connected subgraphs of G. The maximality of all of these parameters is done in a unified way through the use of (n,m) Tutte polynomial posets.