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

preprint2021arXivOpen access

Abstract

Let η(G)η(G) be the number of connected induced subgraphs in a graph GG, and G‾\overline{G} the complement of GG. We prove that η(G)+η(G‾)η(G)+η(\overline{G}) is minimum, among all nn-vertex graphs, if and only if GG has no induced path on four vertices. Since the nn-vertex star SnS_n with maximum degree n−1n-1 is the unique tree of diameter 22, η(Sn)+η(Sn‾)η(S_n)+η(\overline{S_n}) is minimum among all nn-vertex trees, while the maximum is shown to be achieved only by the tree whose degree sequence is (⌈n/2⌉,⌊n/2⌋,1,…,1)(\lceil n/2\rceil,\lfloor n/2\rfloor,1,\dots,1). Furthermore, we prove that every graph GG of order n≥5n\geq 5 and with maximum η(G)+η(G‾)η(G)+η(\overline{G}) must have diameter at most 33, no cut vertex and the property that G‾\overline{G} is also connected. In both cases of trees and graphs that have the same order, we find that if η(G)η(G) is maximum then η(G)+η(G‾)η(G)+η(\overline{G}) is minimum. As corollaries to our results, we characterise the unique connected graph GG of given order and number of vertices of degree 11, and the unique unicyclic (connected and has only one cycle) graphs GG of a given order that minimises η(G)+η(G‾)η(G)+η(\overline{G}).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.