For a graph \(G\), Chartrand et al. defined the rainbow connection number \(rc(G)\) and the strong rainbow connection number \(src(G)\) in “G. Chartrand, G.L. John, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Mathematica Bohemica, \(133(1)(2008) 85-98\)”. They raised the following conjecture: for two given positive integers \(a\) and \(b\), there exists a connected graph \(G\) such that \(rc(G) = a\) and \(src(G) = b\) if and only if \(a = b \in \{1,2\}\) or \(3 \leq a \leq b”\). In this short note, we will show that the conjecture is true.

The graph \(P_{a,b}\) is defined as the one obtained by taking \(b\) vertex-disjoint copies of the path \(P_{a+1}\) of length \(a\), coalescing their first vertices into one single vertex labeled \(u\) and then coalescing their last vertices into another single vertex labeled \(v\). K.M. Kathiresan showed that \(P_{2r,2m-1}\) is graceful and conjectured that \(P_{a,b}\) is graceful except when \((a,b) = (2r+1, 4s+2)\). In this paper, an algorithm for finding another graceful labeling of \(P_{2r,2}\) is provided, and \(P_{2r,2(2k+1)}\) is proved to be graceful for all positive \(r\) and \(k\).

A graph \(G\) is \(\)-extendable if every edge is contained in a perfect matching of \(G\). In this note, we prove the following theorem. Let \(d \geq 3\) be an integer, and let \(G\) be a \(d\)-regular graph of order \(n\) without odd components. If \(G\) is not \(1\)-extendable, then \(n \geq 2d + 4\). Examples will show that the given bound is best possible.

A \(k\)-container \(C(u, v)\) of \(G\) between \(u\) and \(v\) is a set of \(k\) internally disjoint paths between \(u\) and \(v\). A \(k\)-container \(C(u,v)\) of \(G\) is a \(k^*\)-container if it contains all nodes of \(G\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct nodes. The spanning connectivity of \(G\), \(\kappa^*(G)\), is defined to be the largest integer \(k\) such that \(G\) is \(\omega^*\)-connected for all \(1 \leq \omega \leq k\) if \(G\) is an \(1^*\)-connected graph and undefined if otherwise. A graph \(G\) is super spanning connected if \(\kappa^*(G) = \kappa(G)\). In this paper, we prove that the \(n\)-dimensional augmented cube \(AQ_n\) is super spanning connected.

It is the aim of this paper to explore some new properties of the Padovan sequence using matrix methods. We derive new recurrence relations and generating matrices for the sums of Padovan numbers and \(4n\) subscripted Padovan sequences. Also, we define one type of \((0,1)\) upper Hessenberg matrix whose permanents are Padovan numbers.

In this paper, we prove that every \(n\)-cycle (\(n \geq 6\)) with parallel chords is graceful for all \(n \geq 6\) and every \(n\)-cycle with parallel \(P_k\)-chords of increasing lengths is graceful for \(n \equiv 2 \pmod{4}\) with \(1 \leq k \leq \left\lfloor \frac{n}{2} \right\rfloor – 1\).

On the basis of lit.\([9]\), by the joint tree model, the lower bound of the number of genus embeddings for complete tripartite graph \(K_{n,n,\ell}\) \((\ell \geq m \geq 1)\) is got.

The least common ancestor of two vertices, denoted \(\text{lca}(x, y)\), is a well-defined operation in a directed acyclic graph (dag) \(G\). We introduce \(U_\text{lca}(S)\), a natural extension of \(\text{lca}(x,y)\) for any set \(S\) of vertices. Given such a set \(S_0\), one can iterate \(S_{k+1} = U_\text{lca}(S_k)\) in order to obtain an increasing set sequence. \(G\) being finite, this sequence always has a limit which defines a closure operator. Two equivalent definitions of this operator are given and their relationships with abstract convexity are shown. The good properties of this operator permit to conceive an \(O(n.m)\) time complexity algorithm to calculate its closure. This performance is crucial in applications where dags of thousands of vertices are employed. Two examples are given in the domain of life-science: the first one concerns genes annotations’ understanding by restricting Gene Ontology, the second one deals with identifying taxonomic group of environmental \(DNA\) sequences.

A graph \(G(V,E)\) with order \(p\) and size \(q\) is called \((a,d)\)-edge-antimagic total labeling graph if there exists a bijective function \(f : V(G) \cup E(G) \rightarrow \{1, 2, \ldots, p+q\}\) such that the edge-weights \(\lambda_{f}(uv) = f(u) + f(v) + f(uv)\), \(uv \in E(G)\), form an arithmetic sequence with first term \(a\) and common difference \(d\). Such a labeling is called super if the \(p\) smallest possible labels appear at the vertices. In this paper, we study super \((a, 1)\)-edge-antimagic properties of \(m(P_{4} \square P_{n})\) for \(m, n \geq 1\) and \(m(C_{n} \odot \overline{K_{l}})\) for \(n\) even and \(m, l \geq 1\).

Let \((X, {B})\) be a \(\lambda\)-fold block design with block size \(4\). If a pair of disjoint edges are removed from each block of \(\mathcal{B}\), the resulting collection of \(4\)-cycles \(\mathcal{C}’\) is a partial \(\lambda\)-fold \(4\)-cycle system \((X, \mathcal{C})\). If the deleted edges can be arranged into a collection of \(4\)-cycles \(\mathcal{D}\), then \((X, \mathcal{C} \cup \mathcal{D})\) is a \(\lambda\)-fold \(4\)-cycle system [10]. Now for each block \(b \in {B}\), specify a 1-factorization of \(b\) as \(\{F_1(b), F_2(b), F_3(b)\}\) and define for each \(i = 1, 2, 3\), sets \(\mathcal{C}_i\) and \(\mathcal{D}_i\) as follows: for each \(b \in {B}\), put the \(4\)-cycle \(b \setminus F_i(b)\) in \(\mathcal{C}_i\) and the \(2\) edges belonging to \(F_i(b)\) in \(\mathcal{D}_i\). If the edges in \(\mathcal{D}_i\) can be arranged into a collection of \(4\)-cycles \(\mathcal{D}^*_i\), then \( {M}_i = (X, \mathcal{C}_i \cup \mathcal{D}^*_i)\) is a \(\lambda\)-fold 4-cycle system, called the \(i\)th metamorphosis of \((X, \mathcal{B})\). The full metamorphosis is the set of three metamorphoses \(\{ {M}_1, {M}_2, {M}_3\}\). We give a complete solution of the following problem: for which \(n\) and \(\lambda\) does there exist a \(\lambda\)-fold block design with block size \(4\) having a full metamorphosis into a \(\lambda\)-fold \(4\)-cycle system?