The average size of a connected vertex set of a graph—Explicit formulas and open problems. Issue 1 (3rd November 2020)

• Record Type: Journal Article
• Authors: Vince, Andrew
• Is Part Of: Journal of graph theory. Volume 97:Issue 1(2021)
• Page Start: 82
• Page End: 103
• Publication Date: 2020-11-03
• Subjects: average order of a connected induced subgraph -- connectedness -- enumeration -- graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22643
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Although connectivity is a basic concept in graph theory, the enumeration of connected subgraphs of a graph has only recently received attention. The topic of this paper is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree. For various infinite families of graphs, we investigate the asymptotic behavior of the proportion of vertices in an induced connected subgraph of average order. For ladders and circular ladders, an explicit closed formula is derived for the average order of a connected induced subgraph in terms of the classic Pell numbers. These formulas imply that, asymptotically, 3/4 of the vertices of a ladder or circular ladder, on average, are present in a connected induced subgraph. Results on such infinite families motivate an assortment of open problems.