A \(k\)-circular-distance-two labeling (or \(k\)-c-labeling) of a simple graph \(G\) is a vertex-labeling, using the labels \(0, 1, 2, \ldots, k-1\), such that the “circular difference” (mod \(k\)) of the labels for adjacent vertices is at least two, and for vertices of distance-two apart is at least one. The \(\sigma\)-number, \(\sigma(G)\), of a graph \(G\) is the minimum \(k\) of a \(k\)-c-labeling of \(G\). For any given positive integers \(n\) and \(k\), let \(\mathcal {G}^{\sigma}(n, k)\) denote the set of graphs \(G\) on \(n\) vertices and \(\sigma(G) = k\). We determine the maximum size (number of edges) and the minimum size of a graph \(G \in \mathcal {G}^{\sigma}(n, k)\). Furthermore, we prove that for any value \(p\) between the maximum and the minimum size, there exists a graph \(G \in \mathcal {G}^{\sigma}(n, k)\) of size \(p\). These results are analogues of the ones by Georges and Mauro [4] on distance-two labelings.

We give a parametric representation for generic magic squares. This makes it relatively easy to construct magic squares having desired properties. It also suggests a convenient method for generating and classifying all the magic squares of every given order.

A vertex \(v\) in a digraph \(D\) out-dominates itself as well as all vertices \(u\) such that \((v,u)\) is an arc of \(D\); while \(v\) in-dominates both itself and all vertices \(w\) such that \((w,v)\) is an arc of \(D\). A set \(S\) of vertices of \(D\) is a twin dominating set of \(D\) if every vertex of \(D\) is out-dominated by some vertex of \(S\) and in-dominated by some vertex of \(S\). The minimum cardinality of a twin dominating set is the twin domination number \(\gamma^*(D)\) of \(D\). It is shown that \(\gamma^*(D) \leq \frac{2p}{3}\) for every digraph \(D\) of order \(p\) having no vertex of in-degree \(0\) or out-degree \(0\). Moreover, we give a Nordhaus-Gaddum type bound for \(\gamma^*\), and for transitive digraphs we give a sharp upper bound for the twin domination number in terms of order and minimum degree.

For a graph \(G\), the upper orientable twin domination number \(DOM^*(G)\) is the maximum twin domination number \(\gamma^*(D)\) over all orientations \(D\) of \(G\); while the lower orientable twin domination number \(dom^*(G)\) of \(G\) is the minimum such twin domination number. It is shown that for each graph \(G\) and integer \(c\) with \(dom^*(G) \leq c \leq DOM^*(G)\), there exists an orientation \(D\) of \(G\) such that \(\gamma^*(D) = c\).

For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\}\) and edge set \(\{a_ib_j: 1 \leq i \leq n, j = i,i+1,\ldots, i+k-1 \pmod{n}\}\). In this paper, we give a necessary and sufficient condition for the existence of a \(P_1\) decomposition of \(C_{n,k}\).

We use an array given in H. Kharaghani, “Arrays for orthogonal designs”, J. Combin. Designs, \(8 (2000), 166-173\), to obtain infinite families of \(8\)-variable Kharaghani type orthogonal designs, \(OD(8t; k_1, k_1, k_1, k_1, k_2, k_2, k_2, k_2)\), where \(k_1\) and \(k_2\) must be the sum of two squares. In particular, we obtain infinite families of \(8\)-variable Kharaghani type orthogonal designs, \(OD(8t; k, k, k, k, k, k, k, k)\). For odd \(t\), orthogonal designs of order \(\equiv 8 \pmod{16}\) can have at most eight variables.

We introduce semi quadrangles, which are finite partial linear spaces with a constant number of points on each line, having no ordinary triangles and containing, as minimal circuits, ordinary quadrangles and pentagons, with the additional property that every two non-collinear points are collinear with at least one other point of the geometry. A semi quadrangle is called thick if every point is incident with at least three lines and if every line is incident with at least three points. Thick semi quadrangles generalize (thick) partial quadrangles (see [4]). We will emphasize the special situation of the semi quadrangles which are subgeometries of finite generalized quadrangles. Some particular geometries arise in a natural way in the theory of symmetries of finite generalized quadrangles and in the theory of translation generalized quadrangles, as certain subgeometries of generalized quadrangles with concurrent axes of symmetry; these subgeometries have interesting automorphism groups, see [17] and also [19]. Semi quadrangles axiomatize these geometries. We will present several examples of semi quadrangles, most of them arising from generalized quadrangles or partial quadrangles. We will prove an inequality for semi quadrangles which generalizes the inequality of Cameron [4] for partial quadrangles, and the inequality of Higman [7,8] for generalized quadrangles. The proof also gives information about the equality. Some other inequalities and divisibility conditions are computed. Also, we will characterize the linear representations of the semi quadrangles, and we will have a look at the point graphs of semi quadrangles.

Let \(G\) be a graph, \(\overline{G}\) its complement, \(L(G)\) its line graph, and \(\chi(G)\) its chromatic number. Then we have the following

THEOREM Let \(G\) be a graph with \(n\) vertices. (i) If \(G\) is triangle
free, then

\[n-4 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]

(ii) If G is planar and every triangle bounds a disk, then

\[n-3 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]

Let \(G\) be a simple graph on \(n\) vertices with list chromatic number \(\chi_\ell = s\). If each vertex of \(G\) is assigned a list of \(t\) colours, Albertson, Grossman, and Haas [1] asked how many of the vertices, \(\lambda_{t,s}\), are necessarily colourable from these lists? They conjectured that \(\lambda_{t,s} \geq \frac{tn}{s}\). Their work was extended by Chappell [2]. We improve the known lower bounds for \(\lambda_{t,s}\).

In general, the class of threshold hypergraphs and decomposable hypergraphs are not equal. In this paper, we show however that, except for two counter examples, a decomposition hypergraph consisting of five or fewer classes is in fact threshold. In the process of showing this result, the paper generates all decomposable quotients with five or fewer classes.