期刊
ELECTRONIC JOURNAL OF COMBINATORICS
卷 29, 期 1, 页码 1-42出版社
ELECTRONIC JOURNAL OF COMBINATORICS
DOI: 10.37236/9768
关键词
-
资金
- NSF [DMS-1923099, DMS-1922998]
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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据