Suppose that graphs \(H\) and \(G\) are graceful, and that at least one of \(H\) and \(G\) has an \(\alpha\)-labeling. Four graph operations on \(H\) and \(G\) are provided. By utilizing repeatedly or in turn the four graph operations, we can construct a large number of graceful graphs. In particular, if both \(H\) and \(G\) have \(\alpha\)-labelings, then each of the graphs obtained by the four graph operations on \(H\) and \(G\) has an \(\alpha\)-labeling.

In this paper, we present three algebraic constructions of authentication codes from power functions over finite fields with secrecy and realize an application of some properties about authentication codes in [1]. The first and the third class are optimal. Some of the codes in the second class are optimal, and others in the second class are asymptotically optimal. All authentication codes in the three classes provide perfect secrecy.

Compositions and partitions of positive integers are often studied in separate frameworks where partitions are given by \(q\)-series and compositions exhibiting particular patterns are specified by generating functions for these patterns. Here we view compositions as alternating sequences of partitions (i.e., alternating blocks) and obtain results for the asymptotic expectations of the number of such blocks (or parts per block) for different ways of defining the blocks.

For any integer \(k \geq 1\), a signed (total) \(k\)-dominating function is a function \(f : V(G) \rightarrow \{-1, 1\}\) satisfying \(\sum_{u \in N(v)} f(u) > k\) (\(\sum_{w \in N[v]} f(w) \geq k\)) for every \(v \in V(G)\), where \(N(v) = \{u \in V(G) | uv \in E(G)\}\) and \(N[v] = N(v) \cup \{v\}\). The minimum of the values of \(\sum_{v \in V(G)} f(v)\) , taken over all signed (total) \(k\)-dominating functions \(f\), is called the signed (total) \(k\)-domination number and is denoted by \(\gamma_{kS}(G)\) (\(\gamma’_{kS}(G)\), resp.). In this paper, several sharp lower bounds of these numbers for general graphs are presented.

Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices, where any two distinct vertices \(x\) and \(y\) are joined by \(\lambda\) edges \(\{x,y\}\). Let \(G\) be a finite simple graph. A \(G\)-packing design (\(G\)-covering design) of \(K_v\), denoted by \((v,G,\lambda)\)-PD (\((v,G,\lambda)\)-CD) is a pair \((X,B)\), where \(X\) is the vertex set of \(\lambda K_v\) and \(B\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in at most (at least) \(\lambda\) blocks of \(B\). A packing (covering) design is said to be maximum (minimum) if no other such packing (covering) design has more (fewer) blocks. There are four graphs with 7 points, 7 edges and a 5-circle, denoted by \(G_i\), \(i = 1,2,3,4\). In this paper, we have solved the existence problem of the maximum \((v, G_i,\lambda)\)-PD and the minimum \((v, G_i, \lambda)\)-CD.

It was shown by Gaborit et al. [10] that a Euclidean self-dual code over \({GF}(4)\) with the property that there is a codeword whose Lee weight \(\equiv 2 \pmod{4}\) is of interest because of its connection to a binary singly-even self-dual code. Such a self-dual code over \({GF}_4\) is called Type I. The purpose of this paper is to classify all Type I codes of lengths up to 10 and extremal Type I codes of length 12, and to construct many new extremal Type I codes over \({GF}(4)\) of lengths from 14 to 22 and 34. As a byproduct, we construct a new extremal singly-even self-dual binary [36, 18, 8] code, and a new extremal singly-even self-dual binary [68, 34, 12] code with a previously unknown weight enumerator \(W_2\) for \(\beta = 95\) and \(\gamma = 1\).

Let \(j\) and \(k\) be two positive integers. An \(L(j,k)\)-labeling of a graph \(G\) is an assignment of nonnegative integers to the vertices of \(G\) such that the difference between labels of any two adjacent vertices is at least \(j\), and the difference between labels of any two vertices that are at distance two apart is at least \(k\). The minimum range of labels over all \(L(j,k)\)-labelings of a graph \(G\) is called the \(\lambda_{j,k}\)-number of \(G\), denoted by \(\lambda_{j,k}(G)\). Similarly, we can define \(L(j,k)\)-edge-labeling and \(L(j,k)\)-edge-labeling number, \(\lambda’_{j,k}(G)\), of a graph \(G\). In this paper, we show that if \(G\) is \(K_{1,3}\)-free with maximum degree \(\Delta\) then \(\lambda_{j,k}(G) \leq k\lfloor\Delta^2/2\rceil + j\Delta – 1\) except that \(G\) is a 5-cycle and \(j = k\). Consequently, we obtain an upper bound for \(\lambda’_{j,k}(G)\) in terms of the maximum degree of \(L(G)\), where \(L(G)\) is the line graph of \(G\). This improves the upper bounds for \(\lambda’_{2,1}(G)\) and \(\lambda’_{1,1}(G)\) given by Georges and Mauro [Ars Combinatoria \(70 (2004), 109-128]\). As a corollary, we show that Griggs and Yeh’s conjecture that \(\lambda_{2,1}(G) \leq \Delta^2\) holds for all \(K_{1,3}\)-free graphs and hence holds for all line graphs. We also investigate the upper bound for \(\lambda’_{j,k}(G)\) for \(K_{1,3}\)-free graphs \(G\).

Let \(G = (V, E)\) be a hamiltonian graph. A hamiltonian cycle \(C\) of \(G\) is described as \((v_1, v_2, \ldots, v_{n(G)}, v_1)\) to emphasize the order of vertices in \(C\). Thus, \(v_1\) is the beginning vertex and \(v_i\) is the \(i\)-th vertex in \(C\). Two hamiltonian cycles of \(G\) beginning at \(u\), \(C_1 = (u_1, u_2, \ldots, u_{n(G),u_1})\) and \(C_2 = (v_1, v_2, \ldots, v_{n(G)},v_1)\) of \(G\) are independent if \(u_1 = v_1 = u_1\) and \(u_i \neq v_i\) for every \(2 \leq i \leq n(G)\). A set of hamiltonian cycles \(\{C_1, C_2, \ldots, C_k\}\) of \(G\) are mutually independent if they are pairwise independent. The mutually independent hamiltonianicity of graph \(G\), \(\text{IHC}(G)\), is the maximum integer \(k\) such that for any vertex \(u\) there are \(k\)-mutually independent hamiltonian cycles of \(G\) beginning at \(u\). In this paper, we prove that \(\text{IHC}(G) \geq \delta(G)\) for any hamiltonian graph and \(\text{IHC}(G) \geq 2\delta(G) – n(G) + 1\) if \(\delta(G) \geq \frac{n(G)}{2}\). Moreover, we present some graphs that meet the bound mentioned above.

Using connectivity and planarity constraints we characterise all \(5\)-regular planar graphs with diameter \(3\).

In this paper, we investigate how the Wiener index of unicyclic graphs varies with graph operations. These results are used to present a sharp lower bound for the Wiener index of unicyclic graphs of order \(n\) with girth \(g\) and matching number \(\beta \geq \frac{3g}{2}\), Moreover, we characterize all extremal graphs which attain the lower bound.