On maximum graphs in Tutte polynomial posets

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.& COPY; 2023 Elsevier B.V. All rights reserved.