4.2 Article

Computing Volumes of Adjacency Polytopes via Draconian Sequences

期刊

ELECTRONIC JOURNAL OF COMBINATORICS
卷 29, 期 1, 页码 1-42

出版社

ELECTRONIC JOURNAL OF COMBINATORICS
DOI: 10.37236/9768

关键词

-

资金

  1. 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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.2
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据