On the maximum number of connected induced subgraphs of a graph

2023/03/03 by Audace A. V. Dossou-Olory, Dossou-Olory, Audace A. V.
Computer Science · #05C35 #05C69 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Primary 05C30 #secondary 05C40

paper · pdf · doi:10.48550/arxiv.2303.01964

openalex publication_date 2023/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We characterise the structure of those graphs of a given order which maximise the number of connected induced subgraphs for seven different graph classes, each with other prescribed parameters like minimum degree, independence number, vertex cover number, vertex connectivity, edge connectivity, chromatic number, number of bridges, thereby contributing to filling a gap in the literature.

Related

• Graphs and unicyclic graphs with extremal number of connected induced subgraphs
• Cut and pendant vertices and the number of connected induced subgraphs of a graph
• Enumerating Maximal Induced Subgraphs
• Induced subgraphs with many repeated degrees
• On the maximum number of maximum independent sets in connected graphs