The niche graph of a digraph \(D\) is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in \(D\). We define a hierarchy of graphs depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order \(n \geq 3\) having a subgraph isomorphic to \(K_{n-2}\).

Let \(\mathcal{H}_1, \ldots, \mathcal{H}_t\) be classes of graphs. The class Ramsey number \(R(\mathcal{H}_1, \ldots, \mathcal{H}_t)\) is the smallest integer \(n\) such that for each \(t\)-edge colouring \((G_1, \ldots, G_t)\) of \(K_n\), there is at least one \(i \in \{1, \ldots, t\}\) such that \(G_i\) contains a subgraph \(H_i \in \mathcal{H}_i\). We take \(t = 2\) and determine \(R(\mathcal{G}^1_l, \mathcal{G}^1_m)\) for all \(2 \leq l \leq m\) and \(R(\mathcal{G}^2_i, \mathcal{G}^2_{m})\) for all \(3 \leq l \leq m\), where \(\mathcal{G}^i_j\) consists of all edge-minimal graphs of order \(j\) and minimum degree \(i\).

Let \(G\) be a \(2\)-connected graph with a toroidal rotation system given. An algorithm for constructing a straight line drawing with no crossings on a rectangular representation of the torus is presented. It is based on Read’s algorithm for constructing a planar layout of a \(2\)-connected graph with a planar rotation system. It is proved that the method always works. The complexity of the algorithm is linear in the number of vertices of \(G\).

A graph \(G\) is called super-edge-magic if there exists a bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1, 2, \ldots, |V(G)| + |E(G)|\}\) such that \(f(u) + f(v) + f(uv) = C\) is a constant for any \(uv \in E(G)\) and \(f(V(G)) = \{1, 2, \ldots, |V(G)|\}\). In this paper, we show that the generalized Petersen graph \(P(n, k)\) is super-edge-magic if \(n \geq 3\) is odd and \(k = 2\).

We reprove an important case of a recent topological result on improved Bonferroni inequalities due to Naiman and Wynn in a purely combinatorial manner. Our statement and proof involves the combinatorial concept of non-evasiveness instead of the topological concept of contractibility. In contradistinction to the proof of Naiman and Wynn, our proof does not require knowledge of simplicial homology theory.

Quackenbush [5] has studied the properties of squags or “Steiner quasigroups”, that is, the corresponding algebra of Steiner triple systems. He has proved that if a finite squag \((P; \cdot)\) contains two disjoint subsquags \((P_1; \cdot)\) and \((P_2; \cdot)\) with cardinality \(|P_1| = |P_2| = \frac{1}{3} |P|\), then the complement \(P_3 = P – (P_1 \cup P_2)\) is also a subsquag and the three subsquags \(P_1, P_2\) and \(P_3\) are normal. Quackenbush then asks for an example of a finite squag of cardinality \(3n\) with a subsquag of cardinality \(n\), but not normal. In this paper, we construct an example of a squag of cardinality \(3n\) with a subsquag of cardinality \(n\), but it is not normal; for any positive integer \(n \geq 7\) and \(n \equiv 1\) or \(3\) (mod \(6\)).

A plane graph is an embedding of a planar graph into the sphere which may have multiple edges and loops. A face of a plane graph is said to be a pseudo triangle if either the boundary of it has three distinct edges or the boundary of it consists of a loop and a pendant edge. A plane pseudo triangulation is a connected plane graph of which each face is a pseudo triangle. If a plane pseudo triangulation has neither a multiple edge nor a loop, then it is a plane triangulation. As a generalization of the diagonal flip of a plane triangulation, the diagonal flip of a plane pseudo triangulation is naturally defined. In this paper we show that any two plane pseudo triangulations of order \(n\) can be transformed into each other, up to ambient isotopy, by at most \(14n – 64\) diagonal flips if \(n \geq 7\). We also show that for a positive integer \(n \geq 5\), there are two plane pseudo triangulations with \(n\) vertices such that at least \(4n – 15\) diagonal flips are needed to transform into each other.

An extended Mendelsohn triple system of order \(v\) with a idempotent element (EMTS(\(v, a\))) is a collection of cyclically ordered triples of the type \(\{x, y, z\}\), \(\{x, x, y\}\) or \(\{x, x, x\}\) chosen from a \(v\)-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are \(a\) triples of the type \(\{x, x, x\}\). If such a design with parameters \(v\) and \(a\) exist, then they will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). A necessary and sufficient condition for the existence of EMTS(\(v, 0\)) and EMTS(\(v, 1\)) are \(v \equiv 0\) (mod \(3\)) and \(v \not\equiv 0\) (mod \(3\)), respectively. In this paper, we have constructed two EMTS(\(v, 0\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v, 0} – 3, b_{v, 0}\}\), for \(v \equiv 0\) (mod \(3\)). Secondly, we have constructed two EMTS(\(v, 1\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v, 1} – 2, b_{v, 1}\}\), for \(v \not\equiv 0\) (mod \(3\)).