Randomized trial demonstrates structural properties of imbalance graphic graphs, suggesting implications for combinatorial theory.
For an edge uv of a finite simple graph G, its imbalance is |degG(u) - degG(v)|. We prove two structural results on imbalance graphic graphs. First, every finite graph whose edge-containing blocks are regular admits a simple realizing graph indexed by its edges; that is, there is a finite simple graph H with V(H) = E(G) and degH(e) = imbG(e) for every edge e. The proof is constructive: from the block-cut forest we build an auxiliary transition graph, pair opposite half-edges maximally, and use the resulting alternating path components to obtain the realizing graph. This settles Kozerenko and Serdiuk's block-graph conjecture and also implies their conjecture on line graphs of trees. Second, we prove that among finite simple connected bicyclic graphs there is exactly one imbalance non-graphic graph, namely the graph obtained from K4 - e by attaching one leaf to each of the two nonadjacent degree-two vertices. This settles their bicyclic exception conjecture.
No takes yet. Share an insight, caveat, or question.
A. A. Raoui (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: