具有最多与最少连通子图的单圈图

Unicyclic Graphs with Maximal and Minimal Numbers of Connected Subgraphs

树的子树的计数问题被广泛研究,一个自然的问题是研究单圈图的连通子图的计数问题。本文研究单圈图的连通子图数目的极值问题,确定了具有最多与最少连通子图数目的连通单圈图。

The problem of enumeration of subtrees of trees has been extensively studied. A natural problem is to consider the problem of enumeration of connected subgraphs of unicyclic graphs. In this paper, we consider the problem of enumeration of connected subgraphs of unicyclic graphs and we determine the the unicyclic graphs which have the maximal and minimal numbers of connected subgraphs.