×

On maximum graphs in Tutte polynomial posets. (English) Zbl 1528.05036

Summary: F. T. Boesch et al. [Networks 21, No. 2, 181–194 (1991; Zbl 0721.90038)] 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.

MSC:

05C35 Extremal problems in graph theory
05C31 Graph polynomials
05C15 Coloring of graphs and hypergraphs
06A07 Combinatorics of partially ordered sets
90B25 Reliability, availability, maintenance, inspection in operations research
90C35 Programming involving graphs or networks

Citations:

Zbl 0721.90038
Full Text: DOI

References:

[1] Agrawal, A.; Barlow, R., Survey of network reliability and domination theory, Oper. Res., 32, 478-492 (1984) · Zbl 0544.90049
[2] Backman, S., Partial graph orientations and the Tutte polynomial, Adv. Appl. Math., 94, 103-119 (2018) · Zbl 1378.05093
[3] Backman, S.; Hopkins, S., Fourientations and the Tutte polynomial, Res. Math. Sci., 4, 57 (2017), Paper (18) · Zbl 1371.05132
[4] Bauer, D.; Boesch, F.; Suffel, C.; Tindell, R., Combinatorial optimization problems in the analysis and design of probabilistic networks, Networks, 15, 257-271 (1985) · Zbl 0581.90032
[5] Boesch, F. T.; Li, X.; Suffel, C., On the existence of uniformly optimally reliable networks, Networks, 21, 181-194 (1991) · Zbl 0721.90038
[6] Boesch, F.; Satyanarayana, A.; Suffel, C., A survey of some network reliability analysis and synthesis results, Networks, 54, 99-107 (2009) · Zbl 1200.90057
[7] Bollobás, B., Modern graph theory, (Graduate Texts in Mathematics. Vol. 184 (2002), Springer-Verlag: Springer-Verlag New York) · Zbl 1027.05083
[8] Brown, J.; Colbourn, C.; Cox, D.; Graves, C.; Mol, L., Network reliability: Heading out on the highway, Networks, 77, 146-160 (2021) · Zbl 1528.90087
[9] Brown, J.; Cox, D., Nonexistence of optimal graphs for all terminal reliability, Networks, 63, 146-153 (2014) · Zbl 1386.05188
[10] Brylawski, T.; Oxley, J., The tutte polynomial and its applications, (Matroid Applications, Encyclopedia of Mathematics and Its Applications (1992), Cambridge University Press) · Zbl 0769.05026
[11] Cheng, C., Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimization design theory, J. Combin. Theory Ser. B, 31, 240-248 (1981) · Zbl 0475.05050
[12] Colbourn, C., The Combinatorics of Network Reliability (1987), Oxford University Press
[13] Colbourn, C.; Harms, D.; Myrvold, W., Reliability polynomials can cross twice, J. Franklin Inst., 330, 629-633 (1993) · Zbl 0825.93076
[14] Ellis-Monaghan, J.; Merino, C., Graph polynomials and their applications I: The Tutte polynomial, (Structural Analysis of Complex Networks (2011), Birkhauser/Springer: Birkhauser/Springer New York), 219-255 · Zbl 1221.05002
[15] Gessel, I.; Sagan, B., The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin., 3, 2, 36 (1996), Research Paper 9 · Zbl 0857.05046
[16] Green, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions and orientations of graphs, Trans. Am. Math. Soc., 280, 97-126 (1983) · Zbl 0539.05024
[17] Haggard, G.; Pearce, D.; Royle, G., Computing Tutte polynomials, ACM Trans. Math. Software, 37, 3, 17 (2010), Art. 24 · Zbl 1364.05072
[18] Kahl, N., Extremal graphs for the Tutte polynomial, J. Combin. Theory Ser. B, 152, 121-152 (2022) · Zbl 1478.05081
[19] Kelmans, A. K., On graphs with randomly deleted edges, Acta. Math. Acad. Sci. Hung., 37, 77-88 (1981) · Zbl 0503.05056
[20] Kelmans, A., Crossing properties of graph reliability functions, (English Summary) J. Graph Theory, 35, 206-221 (2000) · Zbl 0964.05060
[21] Las Vergnas, M., Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Math., 20, 51-61 (1977) · Zbl 0404.05017
[22] Merino, C., Chip firing and the Tutte polynomial, Ann. Comb., 1, 253-259 (1997) · Zbl 0901.05004
[23] Myrvold, W.; Cheung, K.; Page, L.; Perry, J. A., Uniformly most reliable networks do not always exist, Networks, 21, 417-419 (1991) · Zbl 0729.90045
[24] Oxley, J.; Welsh, D. J.A., The Tutte polynomial and percolation, (Graph Theory and Related Topics (1979), Academic Press: Academic Press New York-London), 329-339 · Zbl 0498.05018
[25] Romero, P., Uniformly optimally reliable graphs: A survey, Networks, 80, 466-481 (2022) · Zbl 1533.05267
[26] Stanley, R., Acyclic orientations of graphs, Discrete Math., 5, 171-178 (1973) · Zbl 0258.05113
[27] Wang, Z., A proof of Boesch’s conjecture, Networks, 25, 277-284 (1994) · Zbl 0826.90060
[28] Welsh, D. J.A., The Tutte polynomial. statistical physics methods in discrete probability, combinatorics, and theoretical computer science, Random Struct. Algorithms, 15, 210-228 (1999) · Zbl 0934.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.