标题： 仙人掌图的子路径数目 显示英文标题

标题： The subpath number of cactus graphs

摘要： 图 \$G\$ 的子路径数被定义为其所有子路径的总数，它与树的数量密切相关，这是图论中一个研究较多的主题。本文是我们之前发表的论文 [5] 的延续，在该文中我们研究了子路径数，并确定了树类、单圈图类、二部图类和圈链类中的极值图。在这里，我们将重点放在仙人掌图的子路径数上，并刻画了具有 \$n\$ 个顶点和 \$k\$ 个圈的所有极大和极小仙人掌图。 我们证明了极大仙人掌图是圈链，其中所有内部圈都是三角形，而两端圈的长度相差最多为一。相比之下，极小仙人掌图由 \$k\$ 个共享公共顶点的三角形组成，其余顶点形成一棵附着在这个公共顶点上的树。 通过比较关于子路径数的极值仙人掌图与关于子树数和 Wiener 指标的极值仙人掌图，我们表明子路径数与这两个量均无相关性，因为它们对应的极值图不同。 显示英文摘要

摘要： 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.