On the maximum number of connected induced subgraphs of a graph

arXiv2303.01964MaRDI QIDQ6428299FDOQ6428299

Publication date: 3 March 2023

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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: On the maximum number of connected induced subgraphs of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428299)