A distance two labelling (or coloring) is a vertex labelling with constraints on vertices within distance two, while the regular vertex coloring only has constraints on adjacent vertices (i.e. distance one). In this article, we consider three different types of distance two labellings. For each type, the minimum span, which is the minimum range of colors used, will be explored. Upper and lower bounds are obtained. Graphs that attain those bounds will be demonstrated. The relations among the minimum spans of these three types are studied.

Arcs and linear maximum distance separable \((M.D.S.)\) codes are equivalent objects~\([25]\). Hence, all results on arcs can be expressed in terms of linear M.D.S. codes and conversely. The list of all complete \(k\)-arcs in \(\mathrm{PG}(2,q)\) has been previously determined for \(q \leq 16\). In this paper, (i) all values of \(k\) for which there exists a complete \(k\)-arc in \(\mathrm{PG}(2,q)\), with \(17 \leq q \leq 23\), are determined; (ii) a complete \(k\)-arc for each such possible \(k\) is exhibited.

An \((r,s; m,n)\)-de Bruijn array is a periodic \(r \times s\) binary array in which each of the different \(m \times n\) matrices appears exactly once. C.T. Fan, S.M. Fan, S.L. Ma and M.K. Siu established a method to obtain either an \((r,2^n;m+1,n)\)-array or a \((2r,2^{n-1};m+1,n)\)-array from an \((r,s; m, n)\)-array. A class of square arrays are constructed by their method. In this paper, decoding algorithms for such arrays are described.

An \(H\)-transformation on a simple \(3\)-connected cubic planar graph \(G\) is the dual operation of flip flop on the triangulation \(G^*\) of the plane, where \(G^*\) denotes the dual graph of \(G\). We determine the seven \(3\)-connected cubic planar graphs whose \(H\)-transformations are uniquely determined up to isomorphism.

Conditions are given for decomposing \(K_{m,n}\) into edge-disjoint copies of a bipartite graph \(G\) by translating its vertices in the bipartition of the vertices of \(K_{m,n}\). A construction of the bipartite adjacency matrix of the \(d\)-cube \(Q_d\) is given leading to a convenient \(\alpha\)-valuation and a proof that \(K_{d2^{d-2},d2^{d-1}}\) can be decomposed into copies of \(Q_d\) for \(d > 1\).

Let \(G\) be a connected graph of order \(n\) and let \(k\) be a positive integer with \(kn\) even and \(n \geq 8k^2 + 12k + 6\). We show that if \(\delta(G) \geq k\) and \(\max\{d(u), d(v)\} \geq n/2\) for each pair of vertices \(u,v\) at distance two, then \(G\) has a \(k\)-factor. Thereby a conjecture of Nishimura is answered in the affirmative.

A graph \(G = (V, E)\) is called \(E\)-cordial if it is possible to label the edges with the numbers from the set \(N = \{0,1\}\) and the induced vertex labels \(f(v)\) are computed by \(f(v) = \sum_{\forall u} f(u,v) \pmod{2}\), where \(v \in V\) and \(\{u,v\} \in E\), so that the conditions \( |v_f(0)| – |v_f(1)| \leq 1\) and \(\big| |e_f(0)| – |e_f(1)| \leq 1\) are satisfied, where \(|v_f(i)|\) and \(|e_f(i)|\), \(i = 0,1\), denote the number of vertices and edges labeled with \(0\)’s and \(1\)’s, respectively. The graph \(G\) is called \(E\)-cordial if it admits an \(E\)-cordial labeling. In this paper, we investigate \(E\)-cordiality of several families of graphs, such as complete bipartite graphs, complete graphs, wheels, etc.

Suppose \(G\) and \(G’\) are graphs on the same vertex set \(V\) such that for each \(v \in V\) there is an isomorphism \(\theta_x\) of \(G-v\) to \(G’-v\). We prove in this paper that if there is a vertex \(x \in V\) and an automorphism \(\alpha\) of \(G-x\) such that \(\theta_x\) agrees with \(\alpha\) on all except for at most three vertices of \(V-x\), then \(G\) is isomorphic to \(G’\). As a corollary we prove that if a graph \(G\) has a vertex which is contained in at most three bad pairs, then \(G\) is reconstructible. Here a pair of vertices \(x,y\) of a graph \(G\) is called a bad pair if there exist \(u,v \in V(G)\) such that \(\{u,v\} \neq \{x,y\}\) and \(G-\{x,y\}\) is isomorphic to \(G-\{u,v\}\).