In this paper, we develop an \(O(k^9 V^6)\) time algorithm to determine the cyclic edge connectivity of \(k\)-regular graphs of order \(V\) for \(k \geq 3\), which improves upon a previously known algorithm by Lou and Wang.

A graph \(G\) is called an \(L_1\)-graph if, for each triple of vertices \(u\), \(v\), and \(w\) with \(d(u,v) = 2\) and \(w \in N(u) \cap N(v)\), the condition \(d(u) + d(v) > |N(u) \cup N(v) \cup N(w)| – 1\) holds. This paper presents two results on the hamiltonicity of \(L_1\)-graphs.

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.

We investigate the conditions under which an association scheme exists on the set of lines of a regular near hexagon with quads of order \((s, t_2)\) passing through every two points at distance \(2\). Specifically, we determine all regular near hexagons admitting such an association scheme when \(s \geq t_2\), while the case \(t^2 > s\) remains open.

Let \(G\) be a connected graph of order \(n\) with Laplacian eigenvalues \(\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n = 0\). The Laplacian-energy-like invariant (\(LEL\) for short) of \(G\) is defined as \(\text{LEL} = \sum_{i=1}^{n-1} \sqrt{\mu_i}\). In this paper, we investigate the asymptotic behavior of the \(LEL\) of iterated line graphs of regular graphs. Furthermore, we derive the exact formula and asymptotic formula for the \(LEL\) of square, hexagonal, and triangular lattices with toroidal boundary conditions.

Let \(S_{r,l}\) be a generalized star on \(rl+1\) vertices with central vertex \(v\). Let \(H_v\) be a graph of order \(m\) with a specified vertex \(v\) of degree \(m-1\). For simple connected graphs \(G_{r,l,H_v}\), obtained by attaching \(v\) of \(H_v\) to each vertex of \(S_{r,l}\) except the central vertex, we derive the adjacency, Laplacian, and signless Laplacian spectrum of \(G_{r,l,H_v}\) in terms of the corresponding spectrum of \(S_{r,l}\) and \(H_v\). Furthermore, we extend these results to obtain the adjacency, Laplacian, and signless Laplacian characteristic polynomials of general graphs.

An important invariant of an interconnection network is its surface area, the number of nodes at distance \(i\) from a node. We derive explicit formulas, via two different approaches: direct counting and generating function, for the surface areas of the alternating group graph and the split-star graph, two Cayley graphs that have been
proposed to interconnect processors in a parallel computer.

This paper is based on the splitting operation for binary metroids that was introduced by Raghunathan, Shikare, and Waphare [Discrete Math. \(184 (1998), p.267-271\)] as a natural generalization of the corresponding operation in graphs. In this paper, we consider the problem of determining precisely which cographic matroids \(M\) have the property that the splitting operation, by every pair of elements,on \(M\) yields a cographic matroid. This problem is solved by proving that there are exactly five minor-minimal matroids that do not have this property.

In 2003, Li introduced the concept of implicit weighted degree, denoted by \(id^w(v)\) for a vertex \(v\) in a weighted graph. In this paper, we prove that: Let \(G\) be a 2-connected weighted graph satisfying: (a) the implicit weighted degree sum of any three independent vertices is at least \(m\); (b) for each induced claw, modified claw, and FP, all edges have the same weight. Then \(G\) contains either a hamiltonian cycle or a cycle of weight at least \(\frac{2}{3}m\).

The Fibonacci \((p, r)\)-cube is an interconnection topology that unifies various connection topologies, including the hypercube, classical Fibonacci cube, and postal network. While classical Fibonacci cubes are known to be partial cubes, we demonstrate that a Fibonacci \((p, r)\)-cube is a partial cube if and only if either \(p = 1\) or \(p \geq 2\) and \(r \leq p + 1\). Furthermore, we establish that for Fibonacci \((p, r)\)-cubes, the properties of being almost-median graphs, semi-median graphs, and partial cubes are equivalent.