The Minimal Kirchhoff Index of Graphs with $k$ Edge-Disjoint Cycles

Abstract

Let $S_n(k;|C_1|,\dots ,|C_k|)$ ($k\ge 3$) denote the $n$-vertex connected graph obtained from $k$ cycles $C_1,\dots ,C_k$ with a unique common vertex by attaching $n–\sum _i|C_i|+k–1$ pendent edges to it. In this paper, we show that among all $n$-vertex graphs with $k$ edge-disjoint cycles, the following graphs have minimal Kirchhoff indices: (i) for $n\le 12$, $S_7(3;3,3,3)$, $S_8(3;3,3,4)$, $S_9(3;3,4,4)$, $S_n(3;4,4,4)$ ($n=10,11$), $S_{12}(3;3,3,3)$, $S_{12}(3;3,3,4)$, $S_{12}(3;3,4,4)$, $S_{12}(3;4,4,4)$, $S_9(4;3,3,3,3)$, $S_{10}(4;3,3,3,4)$, $S_{11}(4;3,3,4,4)$, $S_{12}(4;3,3,3,3)$, $S_{12}(4;3,3,3,4)$, $S_{12}(4;3,3,4,4)$, $S_{12}(4;3,4,4,4)$, $S_{11}(5;3,3,3,3,3)$, $S_{12}(5;3,3,3,3,3)$, $S_{12}(5;3,3,3,3,4)$; (ii) for $n>12$, $S_n(k;3,\dots ,3)$. Additionally, we obtain lower bounds for the Kirchhoff index of $n$-vertex graphs with $k$ edge-disjoint cycles.