查看“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个三角形组成，这些三角形共享一个公共顶点，其余顶点形成一个附着于该公共顶点的树。通过比较子路径数的极值仙人掌图与子树数和[[维纳指数]]的极值图，我们证明了子路径数与这两个量不相关，因为它们的极值图不同。