A Geometric View of Combinatorial Fiedler Theory
2026-07-01 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors build on recent work by Andrade and Dahl, who studied a graph parameter related to the smallest value of a certain function inspired by the graph's connectivity. They explore the opposite problem—maximizing this function—and find that the maximum value corresponds exactly to the average of the two highest vertex degrees in the graph. To explain these problems, the authors use a geometric shape called a cuboctahedron and show where the best solutions appear on it. They also find that counting all solutions for the maximum problem is computationally very hard, even though the maximum value itself is easy to find.
graph theoryalgebraic connectivityRayleigh quotientLaplacian eigenvaluevertex degreecuboctahedroncombinatorial optimizationpolyhedron#P-complete complexity
Authors
José Fernández Goycoolea, Andrea de las Heras-Parrilla, Luis H. Herrera, Clemens Huemer, Carlos Seara
Abstract
Recently, Andrade and Dahl introduced combinatorial Fiedler theory by studying a parameter $b(G)$ defined as the $\ell_1$-analog of the Rayleigh quotient minimization characterization of the algebraic connectivity of a graph $G=(V,E)$. In this work, we study the corresponding maximization problem, which plays the role of the $\ell_1$-analog of the largest Laplacian eigenvalue. We show that the new parameter $B(G)$ associated with this maximization problem admits a simple exact description: it is the average of the two largest vertex degrees of $G$. A unified combinatorial treatment of the minimization and maximization problems is presented first. Later, both optimization problems are reinterpreted in a geometrical setting. The feasible set is identified with a $(n-2)$-dimensional cuboctahedron shell where $n=|V|$. Additional structure is presented for this polyhedron, including the fact that maximizing solutions arise at its vertices and minimizing solutions arise at the centers of its facets. Finally, we analyze the number of optimal vectors for $b(G)$ and $B(G)$ for several graph families. Although the value of $B(G)$ is determined by the two largest degrees, we prove that counting the vectors that attain this value is actually $\#\mathrm{P}$-complete.