Review

Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs

Published in: Quaestiones Mathematicae
Volume 45 , issue 8 , 2022 , pages: 1191–1213

DOI: 10.2989/16073606.2021.1934178

Author(s): Eric O.D. Andriantiana , South Africa , Audace A.V. Dossou-Olory , South Africa

Keywords: Primary: 05C30 , Secondary: 05C05 , 05C35 , Primary: 05C30 , Secondary: 05C05 , 05C35

Abstract

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 degree n − 1 is the unique tree of diameter 2, is minimum among all n-vertex trees, while the maximum is shown to be achieved only by the tree whose degree sequence is (⌈n/2⌉, ⌊n/2⌋, 1, . . . , 1). Furthermore, we prove that every graph G of order n ≥ 5 and with maximum η(G) + η(Ḡ) must have diameter at most 3, no cut vertex and the property that G is also connected. In both cases of trees and graphs that have the same order, we find that if η(G) is maximum then η(G) + η(Ḡ) is minimum.

« Quadratic approximation for some badly rational approximable power series

On the isomorphism of coneat-injective modules over commutative rings »