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

Abstract

Let $\eta (G)$ be the number of connected induced subgraphs in a graph $G$, and $\overline{G}$ the complement of $G$. We prove that $\eta (G)+\eta (\overline{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 $S_n$ with maximum degree $n-1$ is the unique tree of diameter $2$, $\eta (S_n)+\eta (\overline{S_n})$ is minimum among all $n$-vertex trees, while the maximum is shown to be achieved only by the tree whose degree sequence is $(\lceil n/2\rceil ,\lfloor n/2\rfloor ,1,\dots ,1)$. Furthermore, we prove that every graph $G$ of order $n\ge 5$ and with maximum $\eta (G)+\eta (\overline{G})$ must have diameter at most $3$, no cut vertex and the property that $\overline{G}$ is also connected. In both cases of trees and graphs that have the same order, we find that if $\eta (G)$ is maximum then $\eta (G)+\eta (\overline{G})$ is minimum. As corollaries to our results, we characterise the unique connected graph $G$ of given order and number of vertices of degree $1$, and the unique unicyclic (connected and has only one cycle) graphs $G$ of a given order that minimises $\eta (G)+\eta (\overline{G})$.

22 pages, 2 figure, 1 table