Computing Volumes of Adjacency Polytopes via Draconian Sequences

Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The PQ-type adjacency polytope, denoted del(PQ)(G) and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for del(PQ)(G) can be rephrased as counting D(G)-draconian sequences where D (G) is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most 1 and, for 2-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of del(PQ)(G) when G is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs G which are planar but not outerplanar that are worth additional study.

Automated summary

Adjacency polytopes are naturally occurring in the study of nonlinear emergent phenomena in complex networks. This article focuses on the PQ-type adjacency polytope, which encodes combinatorial information about power-flow solutions in sparse power networks. The normalized volume of this polytope provides an upper bound on the number of distinct power-flow solutions. The article presents formulas for computing the normalized volumes for different types of graphs, and also identifies certain planar graphs that are worth further study.