In this paper, we obtain critical sets for the general dihedral group, but we are not able to decide whether they are minimal. We also show the existence of a weakly completable critical set in the latin square based on the dihedral group of order six. We believe this to be the smallest group-based square to have such a set.

An \(S_h\)-set (mod \(m\)) is a set \(S\) of integers such that the sums\(a_1 + a_2 + \cdots + a_h\) of elements \(a_1 \leq a_2 \leq \cdots 1\) and prove that equality is possible at least when \(h=p\) is a prime (Theorem).

We investigate those classes \(\mathcal{K}\) of relational structures closed under operations that are defined by excluding a fixed class of finite structures. We characterize such classes and show they contain an infinite family of pairwise non-embeddable members. NEC structures are defined by certain extension conditions. We construct countable universal structures in \(\mathcal{K}\) satisfying only finitely many of the NEC extension conditions.

The notion of normal quotient of a vertex-transitive graph was introduced in [5]. It was shown there that many graph properties are inherited by normal quotients. The definition of a normal quotient was given in [5] in group-theoretical terms. In this note we give a combinatorial approximation to this notion which extends the original definition. We show that many of the properties that were inherited by group-theoretical normal quotients are also inherited by combinatorial ones.

A \((k;g)\)-cage is a smallest \(k\)-regular graph with girth \(g\). Harary and Kovacs [2] conjectured that for all \(k \geq 3\) and odd \(g \geq 5\), there exists a \((k;g)\)-cage which contains a cycle of length \(g+1\). Among other results, we prove the conjecture for all \(k \geq 3\) and \(g \in \{5,7\}\).

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min{\left\{\frac{|S|}{\omega(G-S)} \mid S \subset V(G), \omega(G-S) \geq 2\right\}}\]

where \(\omega(G-S)\) is the number of components of \(G-S\). We also define \(t(K_n) = +\infty\) for every \(n\).

In this article, we discuss the toughness of the endline graph of a graph and the middle graph of a graph.

We present several new non-isomorphic one-factorizations of \(K_{36}\) and \(K_{40}\) which were found through hill-climbing and testing Skolem sequences. We also give a brief comparison of the effectiveness of hill-climbing versus exhaustive search for perfect one-factorizations of \(K_{2n}\) for small values of \(2n\).

We prove that all cycles are edge-magic, thus solving a problem presented by [2]. In [3] it was shown that all cycles of odd length are edge-magic. We give explicit constructions that show that all cycles of even length are edge-magic. Our constructions differ for the case of cycles of length \(n \equiv 0 \pmod{4}\) and \(n \equiv 2 \pmod{4}\).

We present results that characterize the covering number and the rank partition of the dual of a matroid \(M\) using properties of \(M\). We prove, in particular, that the elements of covering number \(2\) in \(M^*\) are the elements of the closure of the maximal \(2\)-transversals of \(M\).

From the results presented it can be seen that every matroid \(M\) is a weak map image of a transversal matroid with the same rank partition.

Let \(G\) be a spanning subgraph of \(K_{s,s}\), and let \(H\) be the complement of \(G\) relative to \(K_{s,s}\),; that is, \(K_{s,s} = G \ oplus H\) is a factorization of \(K_{s,s}\). For a graphical parameter \(\mu(G)\), a graph \(G\) is \(\mu(G)\)-critical if \(\mu(G + e) < \mu(G)\) for every \(e\) in the ordinary complement \(\bar{G}\) of \(G\), while \(G\) is \(\mu(G)\)-critical relative to \(K_{s,s}\) if \(\mu(G + e) < \mu(G)\) for all \(e \in E(H)\). We show that no tree \(T\) is \(\mu(T)\)-critical and characterize the trees \(T\) that are \(\mu(T)\)-critical relative to \(K_{s,s}\), where \(\mu(T)\) is the domination number and the total domination number of \(T\).

The star graph \(S_n\) and the alternating group graph \(A_n\) are two popular interconnection graph topologies. \(A_n\) has a higher connectivity while \(S_n\) has a lower degree, and the choice between the two graphs depends on the specific requirement of an application. The degree of \(S_n\) can be even or odd, but the degree of \(A_n\) is always even. We present a new interconnection graph topology, split-star graph \(S^2_{n}\), whose degree is always odd. \(S^2_{n}\) contains two copies of \(A_n\) and can be viewed as a companion graph for \(A_n\). We demonstrate that this graph satisfies all the basic properties required for a good interconnection graph topology. In this paper, we also evaluate \(S_n\), \(A_n\), and \(S^2_{n}\) with respect to the notion of super connectivity and super edge-connectivity.

We construct a small table of lower bounds for the maximum number of mutually orthogonal frequency squares of types \(F(n; \lambda)\) with \(n \leq 100\).

A graph \(G\) is \(\{R, S\}\)-free if \(G\) contains no induced subgraphs isomorphic to \(R\) or \(S\). The graph \(Z_1\) is a triangle with a path of length \(1\) off one vertex; the graph \(Z_2\) is a triangle with a path of length \(2\) off one vertex. A graph that is \(\{K_{1,3}, Z_1\}\)-free is known to be either a cycle or a complete graph minus a matching. In this paper, we investigate the structure of \(\{K_{1,3}, Z_2\}\)-free graphs. In particular, we characterize \(\{K_{1,3}, Z_2\}\)-free graphs of connectivity \(1\) and connectivity \(2\).

The problem is to determine the number of `cops’ needed to capture a `robber’ where the game is played with perfect information with the cops and the robber alternating moves. The `cops’ capture the `robber’ if one of them occupies the same vertex as the robber at any time in the game. Here we show that a graph with strong isometric dimension two requires no more than two cops.

Combinatorial properties of the multi-peg Tower of Hanoi problem on \(n\) discs and \(p\) pegs are studied. Top-maps are introduced as maps which reflect topmost discs of regular states. We study these maps from several points of view. We also count the number of edges
in graphs of the multi-peg Tower of Hanoi problem and in this way obtain some combinatorial identities.

A given nonincreasing sequence \(\mathcal D = (d_1, d_2, \dots, d_n)\) is said to contain a (nonincreasing) repetition sequence \(\mathcal D ^* = (d_{i_1},d_{i_2} \dots, d_{i_k})\) for some \(k \leq n – 2\) if all values of \(\mathcal D – \mathcal D ^*\) are distinct and for any \(d_{i_i} \in \mathcal D ^*\), there exists some \(d_t \in \mathcal D – \mathcal D ^*\) such that \(d_{i_1} = d_t\). For any pair of integers \(n\) and \(k\) with \(n \geq k + 2\), we investigate the existence of a graphic sequence which contains a given repetition sequence. Our main theorem contains the known results for the special case \(d_{i_1} = d_{i_k}\) if \(k = 1\) or \(k = 2\) (see [1, 5, 2]).

It is shown that the necessary conditions are sufficient for the existence of \(c\)-BRD(\(v, 3, \lambda\)) for all \(c \geq -1\). This was previously known for \(c = 0\) and for \(c = 1\).

Let \(\mathcal{S}\) be the set of vectors \(\{{e^{i\theta}}:\theta=0, \frac{n}{3}, \frac{2n}{3}\}\), and let \(\mathcal{S}\) be a nonempty simply connected union of finitely many convex polygons whose edges are parallel to vectors in \(\mathcal{S}\). If every three points of \(\mathcal{S}\) see a common point via paths which are permissible (relative to \(\mathcal{S}\)), then \(\mathcal{S}\) is star-shaped via permissible paths. The number three is best possible.

Let \(G\) be a graph with \(n\) vertices and suppose that for each vertex \(v\) in \(G\), there exists a list of \(k\) colors, \(L(v)\), such that there is a unique proper coloring for \(G\) from this collection of lists, then \(G\) is called a uniquely \(k\)-list colorable graph. Recently, M. Mahdian and E.S. Mahmoodian characterized uniquely \(2\)-list colorable graphs. Here, we state some results which will pave the way in characterization of uniquely \(k\)-list colorable graphs. There is a relationship between this concept and defining sets in graph colorings and critical sets in latin squares.

Let \(d_3(n,k)\) be the maximum possible minimum Hamming distance of a ternary linear \([n, k, d; 3]\) code for given values of \(n\) and \(k\). The nonexistence of \([142, 7, 92; 3]\), \([162, 7, 106; 3]\), \([165, 7, 108; 3]\), and \([191, 7, 125; 3]\) codes is proved.

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\)).