An algebraic characterization of strong graphs

Abstract

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 \emph{strong} if $N_i^j(G)\ge N_i^j(H)$ for each pair of integers $i\in \{0,1,\dots ,m\}$ and $j\in \{1,2,\dots ,n\}$ and each connected simple graph $H$ on $n$ vertices and $m$ edges. The graph $G$ is \emph{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.

Proceedings of the 11th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2025)