Title: Invitation to the subpath number Show Chinese title

Title: 邀请到子路径数

Abstract: In this paper we count all the subpaths of a given graph G; including the subpaths of length zero, and we call this quantity the subpath number of G. The subpath number is related to the extensively studied number of subtrees, as it can be considered as counting subtrees with the additional requirement of maximum degree being two. We first give the explicit formula for the subpath number of trees and unicyclic graphs. We show that among connected graphs on the same number of vertices, the minimum of the subpath number is attained for any tree and the maximum for the complete graph. Further, we show that the complete bipartite graph with partite sets of almost equal size maximizes the subpath number among all bipartite graphs. The explicit formula for cycle chains, i.e. graphs in which two consecutive cycles share a single edge, is also given. This family of graphs includes the unbranched catacondensed benzenoids which implies a possible application of the result in chemistry. The paper is concluded with several directions for possible further research where several conjectures are provided. Show Chinese abstract

Abstract: 在本文中，我们计算给定图G的所有子路径的数量；包括长度为零的子路径，并将这个数量称为G的子路径数。子路径数与广泛研究的子树数有关，因为它可以看作是在计数子树时额外要求最大度为二。 我们首先给出了树和单环图的子路径数的显式公式。 我们证明，在具有相同顶点数的连通图中，子路径数的最小值由任何树达到，而最大值由完全图达到。 此外，我们证明，在所有二分图中，顶点集大小几乎相等的完全二分图使子路径数最大。 还给出了循环链的显式公式，即两个连续的循环共享一条边的图。 这类图包括无分支的稠环苯类化合物，这意味着结果可能在化学中有应用。 论文最后给出了几个可能进一步研究的方向，并提出了若干猜想。