An algebraic characterization of strong graphs
Pablo Romero · 2024
Read An algebraic characterization of strong graphs by Pablo Romero (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20702.txt.
Description
Abstract Let G G be a connected simple graph on n n vertices and m m edges. Denote N i ( j ) ( G ) N_{i}^{(j)}(G) the number of spanning subgraphs of G G having precisely i i edges and not more than j j connected components.
Catalog record
| CREATOR | Pablo Romero |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20702
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An algebraic characterization of strong graphs Pablo Romero Abstract Let G G be a connected simple graph on n n vertices and m m edges. Denote N i ( j ) ( G ) N_{i}^{(j)}(G) the number of spanning subgraphs of G G having precisely i i edges and not more than j j connected components. The graph G G is strong if N i j ( G ) ≥ N i j ( H ) N_{i}^{j}(G)\geq N_{i}^{j}(H) for each pair of integers i ∈ { 0 , 1 , … , m } i\in\{0,1,\ldots,m\} and j ∈ { 1 , 2 , … , n } j\in\{1,2,\ldots,n\} and each connected simple graph H H on n n vertices and m m edges. The graph G G is Whitney-maximum if for each connected simple graph H H on n n vertices and m m edges there exists a polynomial P H ( x , y ) P_{H}(x,y) with nonnegative coefficients such that W G ( x , y ) − W H ( x , y ) = ( 1 − x y ) P H ( x , y ) W_{G}(x,y)-W_{H}(x,y)=(1-xy)P_{H}(x,y) , where W G W_{G} and W H W_{H} stand for the Whitney polynomial of G G and H H . In this work it is proved that a graph is strong if and only if it is Whitney-maximum. Consequently, the 0 0 -element conjecture proposed by Boesch [J. Graph Theory 10 (1986), 339–352] is true when restricted to graph classes in which Whitney-maximum graphs exist. 1 Historic motivation During the half of the 20 th century there was a growing interest in two problems that are different in appearance, namely, the 4 -coloring problem and the design of networks with maximum reliability. Some key references in both problems are given in the following paragraphs and the interplay between them is explained, which is the main source of inspiration for this work. On the one hand Birkhoff [ 1 ] , interested in the 4 -coloring problem, defined a univariate polynomial known as the chromatic polynomial for planar graphs. Later works by Whitney [ 14 ] and Tutte [ 13 ] considered generalizations of the chromatic polynomial using bivariate polynomials. The work of Tutte [ 13 ] linked the theory of spanning trees, electrical networks, and graph coloring. In his Ph.D. thesis, he proved the universality property of his eponymous polynomial. Essentially, each graph invariant that obeys the deletion-contraction formula can be obtained by a special evaluation of the Tutte polynomial. The interested reader can consult the recent book [ 4 ] for a rich historic account of the Tutte polynomial and an updated reference in this topic. On the other hand Moore and Shannon [ 10 ] wanted to design highly reliable computers using imperfect electronic components such as relays. The work of Moore and Shannon is considered a point of departure in the study of network reliability. The concept of uniformly most reliable graphs was later introduced by Boesch [ 2 ] . The existence and construction of uniformly most reliable graphs is a current research topic. Boesch et al. [ 3 ] found all uniformly most reliable graphs of corank up to 3 . Curiously enough, the first classes of uniformly most reliable graphs were determined by Kelmans [ 9 ] some years before the definition was formally established in print. In his work he showed that if we remove an arbitrary matching to the complete graph then a uniformly most reliable graph is obtained. The reader can consult the recent survey [ 12 ] for further details. Even though the classical reliability problem aims to find the probability that a graph is connected subject to edge failures, Kelmans [ 9 ] studied a much more general problem in which we are given a positive integer k and the aim is to find the probability that a graph has at most k connected components after each of its edges is independently deleted with given probabilities. This generalization due to Kelmans has not been further explored. The counting problems for the study of graphs having multiple connected components are even harder than the ones that appear in the classical reliability problem faced by Boesch, Moore and Shannon. Joint works of Kahl [ 7 ] , and Kahl and Luttrell [ 8 ] , established links between uniformly most reliable graphs and the Tutte polynomial by means of a novel concept of a Tutte-maximum graph . Using the universality property of the Tutte polynomial it follows that Tutte-maximum graphs are uniformly most reliable graphs. Kahl and Luttrell [ 8 ] then proceeded to recover the results obtained by Boesch et al. on the existence of uniformly most reliable graphs of corank up to 3 but using algebraic methods. Furthermore, Kahl [ 7 ] showed that each Tutte-maximum graph simultaneously attains the extremal value (i.e., minimum or maximum) of several real-valued graph invariants among all graphs with a prescribed number of vertices and edges. The goal of this work is to further explore the interplay between counting problems coming from network reliability analysis and algebraic methods that are available using the Tutte polynomial or Whitney polynomial. This article is organized as follows. A background including some concepts and preliminary results is given in Section 2 . The main result of this work is given in Section 3 , where it is proved that a graph is strong if and only if it is Whitney-maximum. In Section 4 it is proved that the 0 -element conjecture proposed by Boesch [ 2 ] is true when restricted to graph classes in which a Whitney-maximum graph exists. 2 Background In this section we include the concept of Tutte-maximum graph [ 8 ] and some concepts on network reliability. We will also include the 0-element conjecture proposed by Boesch [ 2 ] as well as preliminary results which will be used in the sequel. Let G be a graph on n vertices, m edges and \kappa(G) connected components. The corank of G , denoted c(G) , equals m-n+\kappa(G) . The rank of G , denoted r(G) , equals n-\kappa(G) . Let \mathcal{S}(G) be the set of all spanning subgraphs of G . The Tutte polynomial of G is denoted T_{G}(x,y) and is defined as follows, T_{G}(x,y)=\sum_{H\in\mathcal{S}(G)}(x-1)^{r(G)-r(H)}(y-1)^{c(H)}. (1) The Whitney polynomial of G is defined as W_{G}(x,y)=T_{G}(x+1,y+1) , i.e., W_{G}(x,y)=\sum_{H\in\mathcal{S}(G)}x^{r(G)-r(H)}y^{c(H)}. (2) A bivariate polynomial P(x,y) is nonnegative if there exists nonnegative integers p and q and nonnegative real numbers a_{ij} such that P(x,y)=\sum_{i=0}^{p}\sum_{j=0}^{q}a_{ij}x^{i}y^{j} . Let \mathcal{C}_{n,m} be the set of all connected simple graphs on n vertices and m edges. The concept of Tutte-maximum graphs introduced by Kahl and Luttrell [ 8 ] is a point of departure in the construction of algebraic methods to find uniformly most reliable graphs. Definition 1 . For each pair of graphs G and H in \mathcal{C}_{n,m} we write H\preceq G when T_{G}(x,y)-T_{H}(x,y)=(x+y-xy)P_{H}(x,y) for some nonnegative polynomial P_{H}(x,y) . The graph G is Tutte-maximum if H\preceq G for each H in \mathcal{C}_{n,m} . Now, let us present key concepts from network reliability. Let G be any graph in