The Minimal Kirchhoff Index of Graphs with \(k\) Edge-Disjoint Cycles

Abstract

Let \(S_n(k; |C_1|, \ldots, |C_k|)\) (\(k \geq 3\)) denote the \(n\)-vertex connected graph obtained from \(k\) cycles \(C_1, \ldots, 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 \leq 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, \ldots, 3)\). Additionally, we obtain lower bounds for the Kirchhoff index of \(n\)-vertex graphs with \(k\) edge-disjoint cycles.