2018/12/06 by Audace A. V. Dossou-Olory, Dossou-Olory, Audace A. V. · 1 citation
Computer Science · Mathematics · #05C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #Primary 05C30 #secondary 05C35
paper · pdf · doi:10.48550/arxiv.1812.02422
openalex publication_date 2018/12/06 · openalex created_date 2018/12/11 · openalex updated_date 2026/07/28
Over all graphs (or unicyclic graphs) of a given order, we characterise those graphs that minimise or maximise the number of connected induced subgraphs. For each of these classes, we find that the graphs that minimise the number of connected induced subgraphs coincide with those that are known to maximise the Wiener index (the sum of the distances between all unordered pairs of vertices), and vice versa. For every k, we also determine the connected graphs that are extremal with respect to the number of k-vertex connected induced subgraphs. We show that, in contrast to the minimum which is uniquely realised by the path, the maximum value is attained by a rich class of connected graphs.