We develop a combinatorial model of paperfolding for the purposes of enumeration. A planar embedding of a graph is called a crease pattern if it represents the crease lines needed to fold a piece of paper into something. A flat fold is a crease pattern which lies flat when folded, i.e., can be pressed in a book without crumpling. Given a crease pattern \(C = (V, E)\), a mountain-valley (MV) assignment is a function \(f : E \to \{M, V\}\) which indicates which crease lines are convex and which are concave, respectively. A MV assignment is valid if it doesn’t force the paper to self-intersect when folded. We examine the problem of counting the number of valid MV assignments for a given crease pattern. In particular, we develop recursive functions that count the number of valid MV assignments for flat vertex folds, crease patterns with only one vertex in the interior of the paper. We also provide examples, especially those of Justin, that illustrate the difficulty of the general multivertex case.

An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a \(2\)-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power \(G^k\) (\(k \geq 2\)) of an AT-free graph \(G\) is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs.

We exhibit some problems definable in Feder and Vardi’s logic \(MMSNP\) that are not in the class \(CSP\) of constraint satisfaction problems. Whilst some of these problems have previously been shown to be in \(MMSNP\) (that is, definable in \(MMSNP\)) but not in \(CSP\), existing proofs are probabilistic in nature. We provide explicit combinatorial constructions to prove that these problems are not in \(CSP\) and we use these constructions to exhibit yet more problems in \(MMSNP\) that are not in \(CSP\).

The distance \(d(u,v)\) between a pair of vertices \(u\) and \(v\) is the length of a shortest path joining \(u\) and \(v\). The eccentricity \(e(v)\) of vertex \(v\) is the distance to a vertex farthest from \(v\). In a graph \(G\), an eccentric vertex of \(v\) is a vertex farthest from \(v\), that is, a vertex \(u\) for which \(d(u,v) = e(v)\). Given a set \(X\) of vertices in \(G\), the vertices of \(X\) are mutually eccentric provided that for any pair of vertices \(u\) and \(v\) in \(X\), \(u\) is an eccentric vertex of \(v\) and \(v\) is an eccentric vertex of \(u\). In this paper, we discuss problems concerning sets of mutually eccentric vertices in graphs.

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.