Let \(G = (V, E)\), with \(|V| = n\), be a simple connected graph. An edge-colored graph \(G\) is rainbow edge-connected if any two vertices are connected by a path whose edges are colored by distinct colors. The rainbow connection number of a connected graph \(G\), denoted by \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow edge-connected. In this paper, we obtain tight bounds for \(rc(G)\). We use our results to generalize previous results for graphs with \(\delta(G) \geq 3\).

In this paper, we provide the 4-way combinatorial interpretations of some Rogers–Ramanujan type identities using partitions with “\(n + t\) copies of \(n\)”, lattice paths, \(k\)-partitions, and ordinary partitions.

In this paper, we study the Fibonacci polynomials modulo \(m\) such that \(x^2 = x + 1\) and then we obtain miscellaneous properties of these sequences. Also, we extend the Fibonacci polynomials to the ring of complex numbers. We define the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x) = \{x_i\}\), where \(R\) is a 2-generator ring and \((a,b)\) is a generating pair of the ring \(R\). Furthermore, we obtain the periods of the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x)\) in finite 2-generator rings of order \(p^2\).

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order \(n \geq 12\) and size at least\(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint theta graphs. As a corollary, every graph of order \(n \geq 12\) and size at least \(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil ,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint cycles of even length. The lower bound on the size is sharp in general.

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. A semisymmetric graph must be bipartite whose automorphism group has two orbits of the same size on the vertices. One of our long-term goals is to determine all the semisymmetric graphs of order \(2p^3\), for any prime \(p\). All these graphs \(\Gamma\) with the automorphism group \(Aut(\Gamma)\), are divided into two subclasses: (I) \(Aut(\Gamma)\) acts unfaithfully on at least one bipart; and (II) \(Aut(\Gamma)\) acts faithfully on both biparts. In [9],[19] and [20], a complete classification was given for Subclass (I). In this paper, a partial classification is given for Subclass (II), when \(Aut(\Gamma)\) acts primitively on one bipart.

The notions of \(L\)-tree-coloring and list vertex arboricity of graphs are introduced in the paper, while a sufficient condition for a plane graph admitting an \(L\)-tree-coloring is given. Further, it is proved that every graph without \(K_{5}\)-minors or \(K_{3,3}\)-minors has list vertex arboricity at most \(3\), and this upper bound is sharp.

A model for cleaning a graph with brushes was first introduced by Messinger, Nowakowski, and Pralat in 2008. Later, they focused on the problem of determining the maximum number of brushes needed to clean a graph. This maximum number of brushes needed to clean a graph in the model is called the broom number of the graph. In this paper, we show that the broom number of a graph is equal to the size of a maximum edge-cut of the graph, and prove the \(\mathcal{NP}\)-completeness of the problem of determining the broom number of a graph. As an application, we determine the broom number exactly for the Cartesian product of two graphs.

We give more results in mean cordial and harmonic mean labelings, such as: upper bounds for the number of edges of graphs of given orders for both labelings with direct results, labeling all trees of order \(\leq 9\) to be harmonic mean with the restriction of using the floor function of the definition, and labeling all graphs of order \(\leq 5\) that are harmonic mean graphs without using the label \(q + 1\) in labeling the vertices. Also, we give mean cordial labelings for some families of graphs.

Linkage is very important in Very Large Scale Integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. Thomassen conjectured that every \((2k + 2)\)-connected graph is \(k\)-linked. For \(k \geq 4\), \(K_{3k-1}\) with \(k\) disjoint edges deleted is a counterexample to this conjecture, however, it is still open for \(k = 3\). Thomas and Wollan proved that every \(6\)-connected graph on \(n\) vertices with \(5n – 14\) edges is \(3\)-linked. Hence they obtain that every \(10\)-connected graph is \(3\)-linked. Chen et al. showed that every \(6\)-connected graph with \(K_{9}^-\) as a minor is \(3\)-linked, and every \(7\)-connected graph with \(K_{9}^-\) as a minor is \((2,2k-1)\)-linked. Using a similar method, we prove that every \(8\)-connected graph with \(K_{2k+3}^-\) as a minor is \(4\)-linked, and every \((2k + 1)\)-connected graph with \(K_{2k+3}^-\) as a minor is \((2,2k – 1)\)-linked. Our results extend Chen et al.’s conclusions, improve Thomas and Wollan’s results, and moreover, they give a class of graphs that satisfy Thomassen’s conjecture for \(k = 4\).

Consider any undirected and simple graph \(G = (V, E)\), where \(V\) and \(E\) denote the vertex set and the edge set of \(G\), respectively. Let \(|G| = |V| = n \geq 3\). The well-known Ore’s theorem states that if \(\deg_G(u) + \deg_G(v) \geq n + k\) holds for each pair of nonadjacent vertices \(u\) and \(v\) of \(G\), then \(G\) is traceable for \(k = -1\), Hamiltonian for \(k = 0\), and Hamiltonian-connected for \(k = 1\). In this paper, we investigate any graph \(G\) with \(\deg_G(u) + \deg_G(v) \geq n – 1\) for any nonadjacent vertex pair \(\{u,v\}\) of \(G\), in particular. We call it the \((*)\) condition. We derive four graph families, \(\mathcal{H}_i\), \(1 \leq i \leq 4\), and prove that all graphs satisfying \((*)\) are Hamiltonian-connected unless \(G \in \bigcup_{i=1}^{4} \mathcal{H}_i\). We also establish a comprehensive theorem for \(G\) satisfying \((*)\), which shows that \(G\) is traceable, Hamiltonian, pancyclic, or Hamiltonian-connected unless \(G\) belongs to different subsets of \(\{\mathcal{H}_i | 1 \leq i \leq 4\}\), respectively.