2020/06/01 by Eric Ould Dadah Andriantiana, Andriantiana, Eric Ould Dadah, Audace Amen Vioutou Dossou-Olory +1
Mathematics · #05C05 #05C30 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C30 #msc:05C35
paper · pdf · doi:10.48550/arxiv.2006.01187
22 pages, 2 figure, 1 table
arxiv created 2021/01/16 · arxiv updated 2021/01/19
Let η(G) be the number of connected induced subgraphs in a graph G, and G the complement of G. We prove that η(G)+η(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, η(Sn)+η(Sn) 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,…,1). Furthermore, we prove that every graph G of order n≥ 5 and with maximum η(G)+η(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)+η(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 η(G)+η(G).