For a positive integer \(d \geq 1\), an \(L(d, 1)\)-labeling of a graph \(G\) is an assignment of nonnegative integers to \(V(G)\) such that the difference between labels of adjacent vertices is at least \(d\), and the difference between labels of vertices that are distance two apart is at least \(1\). The span of an \(L(d, 1)\)-labeling of a graph \(G\) is the difference between the maximum and minimum integers used by it. The minimum span of an \(L(d, 1)\)-labeling of \(G\) is denoted by \(\lambda(G)\). In [17], we obtained that \(r\Delta + 1 \leq \lambda(G(rP_5)) \leq r\Delta + 2\), \(\lambda(G(rP_k)) = r\Delta + 1\) for \(k \geq 6\); and \(\lambda(G(rP_4)) \leq (\Delta + 1)r + 1\), \(\lambda(G(rP_3)) \leq (\Delta + 1)r + \Delta\) for any graph \(G\) with maximum degree \(\Delta\). In this paper, we will focus on \(L(d, 1)\)-labelings of the edge-multiplicity-path-replacement \(G(rP_k)\) of a graph \(G\) for \(r \geq 2\), \(d \geq 3\), and \(k \geq 3\). And we show that the class of graphs \(G(rP_k)\) with \(k \geq 3\) satisfies the conjecture proposed by Havet and Yu [7].

Let \(R\) be a commutative ring with non-zero identity. The cozero-divisor graph of \(R\), denoted by \(\Gamma'(R)\), is a graph with vertex-set \(W^*(R)\), which is the set of all non-zero non-unit elements of \(R\), and two distinct vertices \(a\) and \(b\) in \(W^*(R)\) are adjacent if and only if \(a \not\in Rb\) and \(b \not\in Ra\), where for \(c \in R\), \(Rc\) is the ideal generated by \(c\). In this paper, we completely determine all finite commutative rings \(R\) such that \(\Gamma'(R)\) is planar, outerplanar and a ring graph.

The Wiener index is the sum of distances between all pairs of vertices in a connected graph. A cactus is a connected graph in which any two of its cycles have at most one common vertex. In this article, we present some graphic transformations and derive the formulas for calculating the Wiener index of new graphs. With these transformations, we characterize the graphs having the smallest Wiener index among all cacti given matching number and cycle number.

A Roman dominating function on a graph \(G\) is a function \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) of \(G\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) of \(G\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V(G)) = \sum_{u \in V(G)} f(u)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). A graph \(G\) is said to be Roman domination edge critical, or simply \(\gamma_R\)-edge critical, if \(\gamma_R(G + e) < \gamma_R(G)\) for any edge \(e \not\in E(G)\). In this paper, we characterize all \(\gamma_R\)-edge critical connected graphs having precisely two cycles.

An \(h\)-edge-coloring (block-coloring) of type \(s\) of a graph \(G\) is an assignment of \(h\) colors to the edges (blocks) of \(G\) such that for every vertex \(x\) of \(G\), the edges (blocks) incident with \(x\) are colored with \(s\) colors. For every color \(i\), \(\xi_{x,i}\) (\(\mathcal{B}_{x,i}\)) denotes the set of all edges (blocks) incident with \(x\) and colored by \(i\). An \(h\)-edge-coloring (\(h\)-block-coloring) of type \(s\) is equitable if for every vertex \(x\) and for colors \(i\), \(j\), \(||\xi_{x,i}| – |\xi_{x,j}|| \leq 1\) (\(||\mathcal{B}_{x,i}| – |\mathcal{B}_{x,j}|| \leq 1\)). In this paper, we study the existence of \(h\)-edge-colorings of type \(s = 2,3\) of \(K_t\) and then show that the solution of this problem induces the solution of the existence of a \(C_4\)-\(_tK_2\)-design having an equitable \(h\)-block-coloring of type \(s = 2,3\).

G. Chartrand et al. [3] define a graph \(G\) without isolated vertices to be the least common multiple (lcm) of two graphs \(G_1\) and \(G_2\) if \(G\) is a graph of minimum size such that \(G\) is both \(G_1\)-decomposable and \(G_2\)-decomposable. A bi-star \(B_{m,n}\) is a caterpillar with spine length one. In this paper, we discuss a good lower bound for \(lcm(B_{m,n}, G)\), where \(G\) is a simple graph. We also investigate \(lcm(B_{m,n}, rK_2)\) and provide a good lower bound and an appropriate upper bound for \(lcm(B_{m,n}, P_{r+1})\) for all \(m \geq 1\), \(n \geq 1\), and \(r \geq 1\).

A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share the same color. An edge-colored graph \(G\) is rainbow connected if there exists a \(u-v\) rainbow path for any two vertices \(u\) and \(v\) in \(G\). The rainbow connection number of a graph \(G\), denoted by \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow connected. For any two vertices \(u\) and \(v\) of \(G\), a rainbow \(u-v\) geodesic in \(G\) is a rainbow \(u\)–\(v\) path of length \(d(u,v)\), where \(d(u,v)\) is the distance between \(u\) and \(v\). The graph \(G\) is strongly rainbow connected if there exists a rainbow \(u-v\) geodesic for any two vertices \(u\) and \(v\) in \(G\). The strong rainbow connection number of \(G\), denoted by \(src(G)\), is the smallest number of colors that are needed in order to make \(G\) strongly rainbow connected.

In this paper, we determine the precise (strong) rainbow connection numbers of ladders and Möbius ladders. Let \(p\) be an odd prime; we show the (strong) rainbow connection numbers of Cayley graphs on the dihedral group \(D_{2p}\) of order \(2p\) and the cyclic group \(\mathbb{Z}_{2p}\) of order \(2p\). In particular, an open problem posed by Li et al. in [8] is solved.