The chemical antiregular graph conjecture for total $\sigma$-irregularity

A Counterexample to the Chemical Antiregular Graph Conjecture

For a chemical graph $G$ of order $n$, define

$$\sigma_t^{f(n)}(G) = \sum_{\{u,v\}\in\binom{V(G)}2} \lvert d_G(u)-d_G(v)\rvert^{f(n)}.$$

Here a chemical graph is a finite connected simple graph with maximum degree at most $4$.

The chemical antiregular graph conjecture (Conjecture 11 in the source paper) states that the graphs prescribed in Theorem 9 continue to maximize $\sigma_t^{f(n)}$ when $f(n)$ is any constant in the interval $(0,1)$. We disprove this statement for $n=7$ and the constant function

$$f(n)\equiv \frac12.$$

Construction

Let $G$ have vertex set

$$V(G)=\{1,2,3,4,5,6,7\}$$

and edge set

$$\begin{aligned} E(G)=\{&\{1,2\},\{1,3\},\{1,5\},\{1,6\}, \{2,3\},\{2,4\},\\ &\{2,7\},\{3,4\}\}. \end{aligned}$$

The six edges

$$\{1,2\},\ \{1,3\},\ \{1,5\},\ \{1,6\},\ \{2,4\},\ \{2,7\}$$

form a spanning tree of $G$. Hence $G$ is connected. The listed edges are distinct unordered pairs of distinct vertices, so $G$ is simple. The degrees of vertices $1,2,\ldots,7$, in that order, are

$$(4,4,3,2,1,1,1).$$

In particular, $\Delta(G)=4$, so $G$ is a chemical graph. If $a_i$ denotes the number of vertices of degree $i$, then

$$(a_1,a_2,a_3,a_4)=(3,1,1,2).$$

Exact value of the invariant

For $j\in\{1,2,3\}$, let $N_j$ be the number of unordered pairs of vertices whose degrees differ by $j$. For any chemical graph with degree multiplicities $(a_1,a_2,a_3,a_4)$,

$$\begin{aligned} N_1&=a_1a_2+a_2a_3+a_3a_4,\\ N_2&=a_1a_3+a_2a_4,\\ N_3&=a_1a_4. \end{aligned}$$

Pairs of equal-degree vertices contribute $0$. Therefore, when $f(n)=\tfrac12$,

$$\sigma_t^{1/2}=N_1+N_2\sqrt2+N_3\sqrt3.$$

For $G$, the multiplicities $(3,1,1,2)$ give

$$(N_1,N_2,N_3)=(6,5,6),$$

and hence

$$\sigma_t^{1/2}(G)=6+5\sqrt2+6\sqrt3.$$

Comparison with the conjectured maximizers

Since $7=4\cdot2-1$, the degree multiplicities prescribed by Theorem 9 for order $7$ are

$$(a_1,a_2,a_3,a_4)=(2,1,2,2).$$

Let $H$ be any chemical graph with these multiplicities. Because $\sigma_t^{f(n)}$ depends only on the vertex degrees and not on the adjacencies among the vertices, every such $H$ has the same value. Here

$$(N_1,N_2,N_3)=(8,6,4),$$

so

$$\sigma_t^{1/2}(H)=8+6\sqrt2+4\sqrt3.$$

The exact difference is

$$\begin{aligned} \sigma_t^{1/2}(G)-\sigma_t^{1/2}(H) &=(6+5\sqrt2+6\sqrt3)-(8+6\sqrt2+4\sqrt3)\\ &=-2-\sqrt2+2\sqrt3. \end{aligned}$$

This difference is strictly positive. Indeed, all terms below are positive, and therefore squaring preserves the direction of the relevant inequalities:

$$\begin{aligned} 2\sqrt3>2+\sqrt2 &\iff 12>(2+\sqrt2)^2\\ &\iff 12>6+4\sqrt2\\ &\iff 3>2\sqrt2\\ &\iff 9>8. \end{aligned}$$

Consequently,

$$\sigma_t^{1/2}(G) > \sigma_t^{1/2}(H)$$

for every order-$7$ chemical graph $H$ having the degree multiplicities prescribed by Theorem 9.

Conclusion

The function $f(n)\equiv\tfrac12$ is constant and takes its value in $(0,1)$, but the graph $G$ above has strictly larger $\sigma_t^{f(n)}$ than every graph in the class asserted by the conjecture to be maximizing. Therefore the chemical antiregular graph conjecture is false.

This does not contradict Theorem 9 itself. At $n=7$, the hypothesis of that theorem requires

$$f(7)\leq \log_3\!\left(\frac{147}{139}\right) \approx 0.0509358,$$

whereas $f(7)=\tfrac12$. The counterexample instead disproves the conjectured extension of Theorem 9 to constants in $(0,1)$.

Optional exhaustive verification

The preceding exact comparison is already a complete disproof; no computer search is needed. As an independent check, all

$$2^{\binom72}=2^{21}=2{,}097{,}152$$

labeled simple graphs on seven vertices were enumerated. Exactly $859{,}130$ of them are connected and have maximum degree at most $4$. At $f(n)=\tfrac12$, the maximum over these graphs is attained precisely at the degree-multiplicity vector

$$(3,1,1,2),$$

with value

$$6+5\sqrt2+6\sqrt3.$$

Thus the displayed graph is globally optimal among all seven-vertex chemical graphs, although this stronger computational fact is not needed to refute the conjecture.

Reference

M. Knor, R. Škrekovski, S. Filipovski, and D. Dimitrov, “Extremizing antiregular graphs by modifying total $\sigma$-irregularity,” Applied Mathematics and Computation 490 (2025), Article 129199. doi:10.1016/j.amc.2024.129199; arXiv:2411.01530.