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