Turkish Journal of Mathematics
DOI
10.55730/1300-0098.3337
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
First Page
3359
Last Page
3372
Recommended Citation
OLORY, AUDACE A V DOSSOU
(2022)
"Maximising the number of connected induced subgraphs of unicyclic graphs,"
Turkish Journal of Mathematics: Vol. 46:
No.
8, Article 19.
https://doi.org/10.55730/1300-0098.3337
Available at:
https://journals.tubitak.gov.tr/math/vol46/iss8/19
