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.

We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.

In a recent paper [1] Maynard answered a question of Harary and Manvel [2] about the reconstruction of \(square-celled \;animals\). One of his results relied on a general algebraic approach due to Alon, Caro, Krasikov, and Roditty [3]. Applying arguments of a more combinatorial nature we improve this result and give an answer to a question raised by him in [1].