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.