For a bipartite graph the extremal number for the existence of a specific odd (even) length path was determined in J. Graph Theory \(8 (1984), 83-95\). In this article, we conjecture that for a balanced bi-partite graph with partite sets of odd order the extremal number for an even order path guarantees many more paths of differing lengths.The conjecture is proved for a linear portion of the conjectured paths.

Let \(D\) be a primitive digraph. Then there exists a nonnegative integer \(k\) such that there are walks of length \(k\) and \(k+1\) from \(u$ to \(v\) for some \(u,v \in V(D)\) (possibly \(u\) again ). Such smallest \(k\) is called the Lewin index of the digraph \(D\), denoted by \(l(D)\). In this paper, the extremal primitive digraphs with both Lewin index \(n — 2\) and girth \(2\) or \(3\) are determined.

Let \(K_{m} – H\) denote the graph obtained from the complete graph on \(m\) vertices, \(K_{m}\), by removing the edge set \(E(H)\) of \(H\), where \(H\) is a subgraph of \(K_{m}\). In this paper, we characterize the potentially \(K_{6} – 3K_{2}\)-graphic sequences, where \(pK_{2}\) is a matching consisting of \(p\) edges.

In this paper, we investigate a generalized Catalan triangle defined by
\[\frac{k^m}{n} \binom{2n}{n-k}\]
for positive integers \(m\). We then compute weighted half binomial sums involving powers of generalized Fibonacci and Lucas numbers of the form
\[\sum\limits_{k=0}^{n} \binom{2n}{n+k} \frac{k^m}{n}X_{tk}^r,\]
where \(X_n\) either generalized Fibonacci or Lucas numbers, and \(t\) and \(r\) are integers, focusing on cases where \(1 \leq m \leq 6\). Furthermore, we outline a general methodology for computing these sums for larger values of \(m\).

A connected factor \(F\) of a graph \(G\) is a connected spanning subgraph of \(G\). If the degree of each vertex in \(F\) is an even number between \(2\) and \(2s\), where \(s\) is an integer, then \(F\) is a connected even \([2, 2s]\)-factor of \(G\). In this paper, we prove that every supereulerian \(K_{1,\ell+1},K_{1,\ell+1}+e\)-free graph (\(\ell \geq 2\)) contains a connected even \([2, 2\ell – 2]\)-factor.

In \([8]\), Weimin Li and Jianfei Chen studied split graphs such that the monoid of
all endomorphisms is regular. In this paper, we extend the study of \([11]\). We find
conditions such that regular endomorphism monoids of split graphs are completely
regular. Moreover, we find completely regular subsemigroups contained in the
monoid \(End(G)\).

A graph of order \(n\) is said to be \(k\)-factor-critical for non-negative integer \(k \leq n\) if the removal of any \(k\) vertices results in a graph with a perfect matching. For a \(k\)-factor-critical graph of order \(n\), it is called \({trivial}\) if \(k = n\) and \({non-trivial}\) otherwise. Since toroidal graphs are at most non-trivial \(5\)-factor-critical, this paper aims to characterize all non-trivial \(5\)-factor-critical graphs on the torus.

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.