An Algebraic Characterization of Strong Graphs
摘要
Let G be a connected simple graph on n vertices and m edges. Denote \(N_{i}^{(j)}(G)\) the number of spanning subgraphs of G having precisely i edges and not more than j connected components. The graph G is strong if \(N_{i}^{j}(G)\ge N_{i}^{j}(H)\) for each pair of integers \(i\in \{0,1,\ldots ,m\}\) and \(j\in \{1,2,\ldots ,n\}\) and each connected simple graph H on n vertices and m edges. The graph G is Whitney-maximum if for each connected simple graph H on n vertices and m edges there exists a polynomial \(P_H(x,y)\) with nonnegative coefficients such that \(W_{G}(x,y)-W_H(x,y)=(1-xy)P_H(x,y)\) , where \(W_G\) and \(W_H\) stand for the Whitney polynomial of G and H. In this work it is proved that a graph is strong if and only if it is Whitney-maximum. Consequently, the 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.