The average size of a connected vertex set of a graph—Explicit formulas and open problems

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 su...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2021-05, Vol.97 (1), p.82-103
Main Author: Vince, Andrew
Format: Article
Language:English
Subjects:
Apexes
Asymptotic properties
average order of a connected induced subgraph
connectedness
Enumeration
graph
Graph theory
Graphs
Ladders
Layouts
Vertex sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22643