Maximising the number of connected induced subgraphs of unicyclic graphs

Authors: AUDACE A V DOSSOU OLORY

Abstract: Denote by $\mathcal{G}(n,c,g,k)$ the set of all connected graphs of order $n$, having $c$ cycles, girth $g$, and $k$ pendant vertices. In this paper, we give a partial characterisation of the structure of those graphs in $\mathcal{G}(n,c,g,k)$ maximising the number of connected induced subgraphs. For the special case where $c=1$, we find a complete characterisation of all maximal unicyclic graphs. We also derive a precise formula for the corresponding maximum number given the following parameters: (1) order, girth, and number of pendant vertices; (2) order and girth; (3) order.

Keywords: Induced subgraphs, connected graphs, unicyclic graphs, girth, pendant vertices

Full Text: PDF