A path in an edge-coloring graph \(G\), where adjacent edges may be colored the same, is called a \({rainbow\; path}\) if no two edges of \(G\) are colored the same. A nontrivial connected graph \(G\) is \({rainbow\; connected}\) if for any two vertices of \(G\) there is a rainbow path connecting them. The \({rainbow\; connection \;number}\) of \(G\), denoted \(\text{rc}(G)\), is defined as the minimum number of colors by using which there is coloring such that \(G\) is rainbow connected. In this paper, we study the rainbow connection numbers of line graphs of triangle-free graphs, and particularly, of \(2\)-connected triangle-free graphs according to their ear decompositions.

A construction based on Legendre sequences is presented for a doubly-extended binary linear code of length \(2p + 2\) and dimension \(p + 1\). This code has a double circulant structure. For \(p = 4k + 3\), we obtain a doubly-even self-dual code. Another construction is given for a class of triply extended rate \(1/3\) codes of length \(3p + 3\) and dimension \(p + 1\). For \(p = 4k + 1\), these codes are doubly-even self-orthogonal.

A cograph is a \(P_4\)-free graph. We first give a short proof of the fact that \(0\) (\(-1\)) belongs to the spectrum of a connected cograph (with at least two vertices) if and only if it contains duplicate (resp. coduplicate) vertices. As a consequence, we next prove that the polynomial reconstruction of graphs whose vertex-deleted subgraphs have the second largest eigenvalue not exceeding \(\frac{\sqrt{5}-1}{2}\) is unique.

In this paper, we describe Cayley graphs of rectangular bands and normal bands, which are the strong semilattice of rectangular bands, respectively. In particular, we give the structure of Cayley graphs of rectangular bands and normal bands, and we determine which graphs are Cayley graphs of rectangular bands and normal bands.

The generalized Petersen graph \(P(n, k)\) is the graph whose vertex set is \(U \cup W\), where \(U = \{u_0, u_1, \ldots, u_{n-1}\}\), \(W = \{v_0, v_1, \ldots, v_{n-1}\}\); and whose edge set is \(\{u_iu_{i+1},u_iv_{i}, v_iv_{i+k} \mid i = 0, 1, \ldots, n-1\}\), where \(n, k\) are positive integers, addition is modulo \(n\), and \(2 < k < n/2\). G. Exoo, F. Harary, and J. Kabell have determined the crossing number of \(P(n, 2)\); Richter and Salazar have determined the crossing number of the generalized Petersen graph \(P(n, 3)\). In this paper, the crossing number of the generalized Petersen graph \(P(3k, k)\) (\(k \geq 4\)) is studied, and it is proved that \(\text{cr}(P(3k,k)) = k\) (\(k \geq 4\)).

In this paper, we apply the concept of fundamental relation on \(\Gamma\)-hyperrings and obtain some related results. Specially, we show that there is a covariant functor between the category of \(\Gamma\)-hyperrings and the category of fundamental \(\Gamma’/\beta^*\)-rings.

The Merrifield-Simmons index \(\sigma(G)\) of a (molecular) graph \(G\) is defined as the number of independent-vertex sets of \(G\). By \(G(n, l, k)\) we denote the set of unicyclic graphs with girth \(l\) and the number of pendent vertices being \(k\) respectively. Let \(S_n^l\) be the graph obtained by identifying the center of the star \(S_{n-l+1}\) with any vertex of \(C_l\). By \(S^{l,k}_n*\) we denote the graph obtained by identifying one pendent vertex of the path \(P_{n-l-k+1}\) with one pendent vertex of \(S_{l+k}^l\). In this paper, we first investigate the Merrifield-Simmons index for all unicyclic graphs in \(G(n,l,k)\) and \(S^{l,k}_n*\) is shown to be the unique unicyclic graph with maximum Merrifield-Simmons index among all unicyclic graphs in \(G(n, l, k)\) for fixed \(l\) and \(k\). Moreover, we proved that:

1. When \(k = n – 3\), \(S^{3,k}_n\) has the maximum Merrifield-Simmons index among all graphs in \(G(n, k)\); When \(k = 1, n-4\), \(S^{4,k}_n\) or \(S^{n-k,k}_n\) has the maximum Merrifield-Simmons index among all graphs in \(G(n,k)\)
2. When \(2 \leq k \leq n-5\), \(S^{n-k,k}_n\) and \(S^{4,k}_n\) are respectively unicyclic graphs having maximum and second-maximum Merrifield-Simmons indices among all unicyclic graphs in \(G(n, k)\), where \(G(n, k)\) denotes the set of unicyclic graphs with \(n\) vertices and \(k\) pendent vertices.

In this paper, we give a complete solution to the Hamilton-Waterloo problem for the case of Hamilton cycles and \(C_{4k}\)-factors for all positive integers \(k\).

In this paper, we study the edge deletion preserving the diameter of the Johnson graph \(J(n,k)\). Let \(un^-(G)\) be the maximum number of edges of a graph \(G\) whose removal maintains its diameter. For Johnson graph \(J(n,k)\), we give upper and lower bounds to the number \(un^-(J(n,k))\), namely:\(\binom{k}{2}\binom{n}{k+1} \leq un^-(J(n,k)) \leq \binom{k+1}{2} \binom{n}{k+1} + \lceil(1+\frac{1}{2k})(\binom{n}{k} – 1\rceil,\) for \(n \geq 2k \geq 2\).