Graphs and unicyclic graphs with extremal connected subgraphs

Audace A. V. Dossou-Olory

Published 2018-12-06Version 1

Over all graphs or unicyclic graphs of a given order, we characterise all graphs (or unicyclic graphs) that minimise or maximise the number of connected subgraphs or connected induced subgraphs. For each of these classes, we find that the minimal graphs for 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.