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?

Let \(G\) be a nontrivial connected graph of order \(n\), and \(k\) an integer with \(2 \leq k \leq n\). For a set \(S\) of \(k\) vertices of \(G\), let \(\nu(S)\) denote the maximum number \(\ell\) of edge-disjoint trees \(T_1, T_2, \ldots, T_\ell\) in \(G\) such that \(V(T_i) \cap V(T_j) = S\) for every pair \(i, j\) of distinct integers with \(1 \leq i, j \leq \ell\). Chartrand et al. generalized the concept of connectivity as follows: The \(k\)-connectivity, denoted by \(\kappa_k(G)\), of \(G\) is defined by \(\kappa_k(G) = \min\{\nu(S)\}\), where the minimum is taken over all \(k\)-subsets \(S\) of \(V(G)\). Thus \(\kappa_2(G) = \kappa(G)\), where \(\kappa(G)\) is the connectivity of \(G\). Moreover, \(\kappa_n(G)\) is the maximum number of edge-disjoint spanning trees of \(G\).

This paper mainly focuses on the \(k\)-connectivity of complete bipartite graphs \(K_{a,b}\), where \(1 \leq a \leq b\). First, we obtain the number of edge-disjoint spanning trees of \(K_{a,b}\), which is \(\lfloor \frac{ab}{a+b-1}\rfloor \), and specifically give the \(\lfloor \frac{ab}{a+b-1}\rfloor\) edge-disjoint spanning trees. Then, based on this result, we get the \(k\)-connectivity of \(K_{a,b}\) for all \(2 \leq k \leq a + b\). Namely, if \(k > b – a + 2\) and \(a – b + k\) is odd, then \(\kappa_k(K_{a,b}) =\frac{a+b-k+1}{2} \left\lfloor \frac{(a-b + k + 1)(b-a + k – 1)}{4(k-1)} \right\rfloor\), if \(k > b – a + 2\) and \(a – b + k\) is even, then \(\kappa_k(K_{a,b}) = \frac{a+b-k+1}{2} +\left\lceil \frac{(a – b+ k )(a + b – k)}{4(k-1)} \right\rceil\), and if \(k \leq b – a + 2\), then \(\kappa_k(K_{a,b}) = a\).

A labelling of a graph over a field \(\mathbb{F}\) is a mapping of the edge set of the graph into \(\mathbb{F}\). A labelling is called magic if for any vertex, the sum of the labels of all the edges incident to it is the same. The class of all such labellings forms a vector space over \(\mathbb{F}\) and is called the magic space of the graph. For finite graphs, the dimensional structure of the magic space is well known. In this paper, we give the existence of magic labellings and discuss the dimensional structure of the magic space of locally finite graphs. In particular, for a class of locally finite graphs, we give an explicit basis of the magic space.