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.

In this paper, we establish the equivalence between semi-
deterministic virtual finite automaton\((SDVFA)\) of order \((s,t)\) and
and regular grammar.

For a graph \(G\), a \({trail}\) is a vertex-edge alternating sequence \(v_0, e_1, v_1, e_2, \ldots, e_{k-1},v_{k-1}, e_k, v_k\) such that all \(e_i\)’s are distinct and \(e_i = v_{i-1}v_i\) for all \(i\). For \(u, v \in V(G)\), a \((u,v)\)-trail of \(G\) is a trail in \(G\) originating at \(u\) and terminating at \(v\). A closed trail is a \((u,v)\)-trail with \(u = v\). A trail \(H\) is a spanning trail of \(G\) if \(V(H) = V(G)\). Let \(X \subseteq E(G)\) and \(Y \subseteq E(G)\) with \(X \cap Y = \emptyset\). This paper studies the minimum edge-connectivity of \(G\) such that for any \(u, v \in V(G)\) (including \(u = v\)), \(G\) has a spanning \((u, v)\)-trail \(H\) with \(X \subseteq E(H)\) and \(Y \cap E(H) = \emptyset\).

In this paper we settle a long-standing open problem. We prove that it
is \(NP\)-hard to recognize \(T\)-tenacious graphs for any fixed positive rational
number \(T\)