Abstract:We consider embeddings of maximal outerplanar graphs whose vertices all lie on a cycle $\mathcal{C}$ bounding a face. Each edge of the graph that is not in $\mathcal{C}$, a chord, is assigned a length equal to the length of the shortest path in $\mathcal{C}$ between its endpoints. We define the total chord length of a graph as the sum of lengths of all its chords. For each order $n\ge 5$, we find outerplanar graphs whose total chord length is the minimum among all graphs of the same order, and graphs whose total chord length is the maximum among all graphs of the same order. We give a complete characterization of the graphs that attain the maximum total chord length. We show that every integer value in the interval determined by the minimum and maximum values is the total chord length of a maximal outerplanar graph of the same order.
From: Elena Pavelescu [view email]
[v1]
Wed, 17 Apr 2024 03:09:35 UTC (4,950 KB)
[v2]
Wed, 19 Aug 2026 16:50:42 UTC (4,955 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。