Let \(G\) be a simple graph of order \(n\) with \(\mu_1, \mu_2, \ldots, \mu_n\) as the roots of its matching polynomial. Recently, Gutman and Wagner defined the matching energy as \(\sum_{i=1}^{n} |\mu_i|\). In this paper, we first show that the Turán graph \(T_{r,n}\) is the \(r\)-partite graph of order \(n\) with maximum matching energy. Furthermore, we characterize the connected graphs (and bipartite graphs) of order \(n\) having minimum matching energy with \(m\) edges, where \(n+2 \leq m \leq 2n-4\) (and \(n \leq m\leq 2n-5\)).

The smallest bigraph that is edge-critical but not edge-minimal with respect to Hamilton laceability is the Franklin graph. Polygonal bigraphs\(^*\) \(P_{m,}\), which generalize one of the many symmetries of the Franklin graph, share this property of being edge-critical but not edge-minimal \([1]\). An enumeration of Hamilton paths in \(P_{m}\) for small \(m\) reveals surprising regularities: there are \(2^m\) Hamilton paths between every pair of adjacent vertices, \(3 \times 2^{m-2}\) between every vertex and a unique companion vertex, and \(3 \times 2^{m-2}\) between all other pairs. Notably, Hamilton laceability only requires at least one Hamilton path between every pair of vertices in different parts; remarkably, there are exponentially many.

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.