On the Maximum Number of Connected Induced Subgraphs of a Graph (Contemporary Mathematics, 2025)
We characterize the structure of graphs of a given order that maximize the number of connected induced subgraphs across seven different graph classes, each with specific parameters such as minimum degree, independence number, vertex cover number, vertex connectivity, edge connectivity, chromatic number, and the number of bridges. This work contributes to filling a gap in the existing literature.
Keywords: minimum degree, independence number, vertex cover number, vertex connectivity, edge connectivity, number of bridges, chromatic number, connected induced subgraphs