Cheeger constant of some families of graphs

The Cheeger constant, introduced by Jeff Cheeger in 1970, plays a vital role in understanding the connectivity and bottleneck properties of a graph. It serves as a fundamental concept in graph theory and network analysis, especially in partitioning problems and clustering applications in data science, machine learning, and related fields. A large Cheeger constant indicates strong connectivity, while a small value reflects the presence of sparse cuts within the graph structure. The Cheeger constant of some families of graphs, including 2-comb graphs, complete graphs, cubic graphs and quantum graphs such as cycle graphs, butterfly graphs, flower graphs and symmetric flower dumbbell graphs has been studied in the literature. This paper focuses on determining the Cheeger constant of various families of graphs, including path graphs, ladder graphs, Cartesian products of paths with cycles, and roach graphs. Even though finding Cheeger constant for a large graph is non-deterministic-polynomial time-hard hard (NP ) problem, in this research, we derive closed-form formulas for the Cheeger constant using an optimum number of subsets, while varying the number of vertices in the graph. All the considered graphs share a similar structural pattern, with path graphs serving as their subgraphs, which allows for a unified approach in analyzing their Cheeger constants. Calculating the Cheeger constant for these families can help better understand their connectivity and separability. The findings are particularly valuable in applications such as spectral graph theory, network design, and data clustering. This study also highlights the usability of Cheeger constant for analyzing diverse graph families, bridging theoretical insights with practical applications in network partitioning and beyond.