WikiEdge:ArXiv速遞/2025-03-04

摘要

• 原文標題：The subpath number of cactus graphs
• 中文標題：仙人掌圖的子路徑數
• 發布日期：2025-03-04 14:55:49+00:00
• 作者：Martin Knor, Jelena Sedlar, Riste Škrekovski, Yu Yang
• 分類：math.CO, 05C30, 05C38
• 原文鏈接：http://arxiv.org/abs/2503.02683v1

原文摘要：The subpath number of a graph G is defined as the total number of subpaths in G, and it is closely related to the number of subtrees, a well-studied topic in graph theory. This paper is a continuation of our previous paper [5], where we investigated the subpath number and identified extremal graphs within the classes of trees, unicyclic graphs, bipartite graphs, and cycle chains. Here, we focus on the subpath number of cactus graphs and characterize all maximal and minimal cacti with n vertices and k cycles. We prove that maximal cacti are cycle chains in which all interior cycles are triangles, while the two end-cycles differ in length by at most one. In contrast, minimal cacti consist of k triangles, all sharing a common vertex, with the remaining vertices forming a tree attached to this joint vertex. By comparing extremal cacti with respect to the subpath number to those that are extremal for the subtree number and the Wiener index, we demonstrate that the subpath number does not correlate with either of these quantities, as their corresponding extremal graphs differ. 中文摘要：圖的子路徑數定義為圖中所有子路徑的總數，它與子樹數密切相關，後者是圖論中一個被廣泛研究的主題。本文是我們之前論文[5]的延續，在那篇論文中我們研究了子路徑數，並在樹、單環圖、二分圖和環鏈等圖類中識別了極值圖。本文中，我們專注於仙人掌圖的子路徑數，並刻畫了所有具有n個頂點和k個環的極大和極小仙人掌圖。我們證明了極大仙人掌圖是環鏈，其中所有內部環都是三角形，而兩個端環的長度最多相差一。相反，極小仙人掌圖由k個三角形組成，這些三角形共享一個公共頂點，其餘頂點形成一個附着於該公共頂點的樹。通過比較子路徑數的極值仙人掌圖與子樹數和維納指數的極值圖，我們證明了子路徑數與這兩個量不相關，因為它們的極值圖不同。