For a tree \(T\), the set of leaves of \(T\) is denoted by \(Leaf(T)\), and the subtree \(T – Leaf(T)\) is called the \({stem} of T\). We prove that if a connected graph \(G\) either satisfies \(\sigma_{k+1}(G) \geq |G| – k – 1\) or has no vertex set of size \(k+1\) such that the distance between any two of its vertices is at least \(4\), then \(G\) has a spanning tree whose stem has at most \(k\) leaves, where \(\sigma_{k+1}(G)\) denotes the minimum degree sum of \(k+1\) independent vertices of \(G\). Moreover, we show that the condition on \(\sigma_{k+1}(G)\) is sharp. Additionally, we provide another similar sufficient degree condition for a claw-free graph to have such a spanning tree.

We prove that every connected subcubic graph G has two spanning trees \(T_1,T_2\) such that every component of \(G – E(T_1)\) is a path of length at most \(3\), and every component of \(G – E(T_2)\) is either a path of length at most \(2\) or a cycle.

A graph \(X\) is said to be \({End-completely-regular}\) (\({End-inverse}\)) if its endomorphism monoid \(End(X)\) is completely regular (inverse). In this paper, we demonstrate that if \(X + Y\) is End-completely-regular, then both \(X\) and \(Y\) are End-completely-regular. We present several approaches to construct new End-completely-regular graphs via the join of two graphs with specific conditions. Notably, we determine the End-completely-regular joins of bipartite graphs. Furthermore, we prove that \(X + Y\) is End-inverse if and only if \(X + Y\) is End-regular and both \(X\) and \(Y\) are End-inverse. Additionally, we determine the End-inverse joins of bipartite graphs.

The tensor product of two graphs \(G_1\) and \(G_2\), denoted by \(G_1 \times G_2\), is defined as the graph with vertex set \(\{(x, y): x \in V(G_1), y \in V(G_2)\}\) and edge set \(\{(x_1, y_1)(x_2, y_2): x_1x_2 \in E(G_1), y_1y_2 \in E(G_2)\}\). Very recently, Zhang, Zheng, and Mamut showed that if \(\delta(G_1) \geq 2\) and \(G_2\) does not belong to a well-characterized class \(\mathcal{G}\) of graphs, then \(G_1 \times G_2\) admits a nowhere-zero \(3\)-flow. However, it remains unclear whether \(G_1 \times G_2\) admits a nowhere-zero \(3\)-flow if \(\delta(G_1) \geq 2\) and \(G_2\) belongs to \(\mathcal{G}\), especially for the simplest case \(G_2 = K_2\). The main objective of this paper is to show that for any graph \(G\) with \(2 \leq \delta(G) \leq \Delta(G) \leq 3\), \(G \times K_2\) admits a nowhere-zero \(3\)-flow if and only if either every cycle in \(G\) contains an even number of vertices of degree \(2\) or every cycle in \(G\) contains an even number of vertices of degree \(3\). We also extend the sufficiency of this result to graphs \(G \times K_2\), where all odd vertices in \(G\) are of degree \(3\).

The notion of \(SDVFA\) (Strong Deterministic Variable Finite Automaton) of order \((s,t)\) was previously introduced by the author \([12]\). In this paper, we demonstrate the equivalence of \(SDVFA\) of order \((s,t)\) with DFA (Deterministic Finite Automaton), \(VDPA\) (Variable Deterministic Pushdown Automaton), NFA (Nondeterministic Finite Automaton), and \(\epsilon\)-NFA (extended Nondeterministic Finite Automaton). This equivalence is established by presenting conversions between \(SDVFA\) and \(DFA, VDFA, NFA\) (\(\epsilon\)-NFA), and vice versa.

Let \(G = (V, E)\) be a connected graph. \(G\) is \({super-\lambda}\) if every minimum edge cut of \(G\) isolates a vertex. Moreover, an edge set \(S \subseteq E\) is a \({restricted\; edge\; cut}\) of \(G\) if \(G – S\) is disconnected and every component of \(G – S\) has at least \(2\) vertices. The \({restricted \;edge\; connectivity}\) of \(G\), denoted by \(\lambda'(G)\), is the minimum cardinality of all restricted edge cuts. Let \(\xi(G) = \min\{d_G(u) + d_G(v) – 2: uv \in E(G)\}\). We say \(G\) is \({\lambda’-optimal}\) if \(\lambda'(G) = \xi(G)\). In this paper, we provide a sufficient condition for bipartite graphs to be both super-\(\lambda\) and \(\lambda’\)-optimal.

The thickness \(\theta(G)\) of a graph \(G\) is the minimum number of planar spanning subgraphs into which \(G\) can be decomposed. In this note, we determine the thickness of the complete tripartite graph \(K_{l,m,n}\) (\(1 \leq m \leq n\)) for the following cases: (1) \(l + m \leq 5\); (2) \(l + m\) is even and \(n > \frac{1}{2}(l + m – 2)\); (3) \(l + m\) is odd and \(n > (l + m – 2)(l + m – 1)\).

We give an elementary, self-contained, and purely combinatorial proof of the Rayleigh monotonicity property of graphs.

Let \(D = (V, A)\) be a strongly connected digraph. \(D\) is called \(\lambda’\)-optimal if its restricted arc-connectivity equals the minimum arc degree. In this paper, we provide sufficient conditions for digraphs to be \(\lambda’\)-optimal.

In this paper, new families of Pell and Pell-Lucas numbers are introduced. In addition, we present the recurrence relations
and the generating functions of the new families for \(k = 2.\)