Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs
Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs
Let η(G) be the number of connected induced subgraphs in a graph G, and Ḡ the complement of G. We prove that η(G) + η(Ḡ) is minimum, among all n-vertex graphs, if and only if G has no induced path on four vertices. Since the n-vertex star Sn with maximum …