For a graph \(G = (V,E)\), a function \(f : V \rightarrow \{0,1,2\}\) is called a Roman dominating function (RDF) if for any vertex \(v\) with \(f(v) = 0\), there is at least one vertex \(w\) in its neighborhood with \(f(w) = 2\).

The weight of an RDF \(f\) of \(G\) is the value \(f(V) = \sum_{v\in V} f(v)\). The minimum weight of an RDF of \(G\) is its Roman domination number, denoted by \(\gamma_R(G)\). In this paper, we show that \(\gamma_R(G) + 1 \leq \gamma_R(\mu(G)) \leq \gamma_R(G) + 2\), where \(\mu(G)\) is the Mycielekian graph of \(G\), and then characterize the graphs achieving equality in these bounds.

A graph is said to be cordial if it has a \(0-1\) labeling that satisfies certain properties. A fan \(F_n\) is the graph obtained from the join of the path \(P_n\) and the null graph \(N_1\). In this paper, we investigate the cordiality of the join and the union of pairs of fans and graphs consisting of a fan with a path, and a cycle.

We consider the problem of covering a unit cube with smaller cubes. The size of a cube is given by its side length and the size of a covering is the total size of the cubes used to cover the unit cube. We denote by \(g_3(n)\) the smallest size of a minimal covering using \(n\) cubes. We present tight results for the upper and lower bounds of \(g_3(n)\).

Let \(G\) be a graph. The cardinality of any largest independent set of vertices in \(G\) is called the independence number of \(G\) and is denoted by \(\alpha(G)\). Let \(a\) and \(b\) be integers with \(0 \leq a \leq b\). If \(a = b\), it is assumed that \(G\) be a connected graph, furthermore, \(a \geq \alpha(G)\), \(a/|V(G)| = 0 \pmod{2}\) if \(a\) is odd. We prove that every graph \(G\) has an \([a, b]\)-factor if its minimum degree is at least \((\frac{b+\alpha(G)a-\alpha(G)}{b})\lfloor \frac{b+\alpha(G)a}{2\alpha(G)} \rfloor -\frac{\alpha(G)}{b}(\lfloor \frac{b+\alpha(G)a}{2\alpha(G)}\rfloor )^2+ \theta\frac{\alpha(G)^2}{b}+\frac{a}{b}\alpha(G)\), where \(\theta = 0\) if \(a < b\), and \(\theta = 1\) if \(a = b\). This degree condition is sharp.

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\).