On the Maximum Number of Connected Induced Subgraphs of a Graph

Audace A.V.  Dossou-Olory

doi:10.37256/cm.6220255773

On the Maximum Number of Connected Induced Subgraphs of a Graph

Authors

Audace A.V. Dossou-Olory Department of Hydrology and Water Resources Management, National Institute of Water, and African Center of Excellence for Water and Sanitation, University of Abomey-Calavi, Abomey-Calavi, Benin

DOI:

https://doi.org/10.37256/cm.6220255773

Keywords:

minimum degree, independence number, vertex cover number, vertex connectivity, edge connectivity, number of bridges, chromatic number, connected induced subgraphs

Abstract

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.

Downloads

Published

2025-03-17

How to Cite

Dossou-Olory AA. On the Maximum Number of Connected Induced Subgraphs of a Graph. Contemp. Math. [Internet]. 2025 Mar. 17 [cited 2025 Apr. 2];6(2):1888-97. Available from: https://ojs.wiserpub.com/index.php/CM/article/view/5773

Download Citation

Issue

Contemporary Mathematics, Volume 6 Issue 2 (2025)

Section

Research Article

License

This work is licensed under a Creative Commons Attribution 4.0 International License.