Let \( M(b, n) \) be the complete multipartite graph with \( b \) parts \( B_0, \ldots, B_{b-1} \) of size \( n \). A \( 4 \)-cycle system of \( M(b, n) \) is said to be a \({frame}\) if the \( 4 \)-cycles can be partitioned into sets \( S_1, \ldots, S_z \) such that for \( 1 \leq j \leq z \), \( S_j \) induces a \( 2 \)-factor of \( M(b, n) \setminus B_i \) for some \( i \in \mathbb{Z}_b \). The existence of a \( C_4 \)-frame of \( M(b, n) \) has been settled when \( n = 4 \) [6]. In this paper, we completely settle the existence question of a \( C_4 \)-frame of \( M(b, n) \) for all \( b \neq 2 \) and \( n \).

A subset \( A \) of vertices of a graph \( G \) is a \( k \)-dominating set if every vertex not in \( A \) has at least \( k \) neighbors in \( A \) and a \( k \)-star-forming set if every vertex not in \( A \) forms with \( k \) vertices of \( A \) a not necessarily induced star \( K_{1, k} \). The maximum cardinalities of a minimal \( k \)-dominating set and of a minimal \( k \)-star-forming set of \( G \) are respectively denoted by \( \Gamma_k(G) \) and \( \text{SF}_k(G) \). We determine upper bounds on \( \Gamma_k(G) \) and \( \text{SF}_k(G) \) and describe the structure of the extremal graphs attaining them.

Clatworthy described the eleven group divisible designs with three groups, block size four, and replication number at most 10. With these in mind one might ask: Can each of these designs be generalized in natural ways? In two previous papers the existence of natural generalizations of four of these designs were settled. Here we essentially settle the existence of natural generalizations of five of the remaining seven Clatworthy designs.

A complete solution is obtained for the possible number of common entries between two Latin squares of different given orders. This intersection problem assumes the entries of the smaller square are also entries of the larger, and that, for comparison, the smaller square is overlayed on the larger. However, these extra restrictions do not affect the solution, apart from one small example.

Let \( G = (V, E) \) be a graph. A subset \( S \) of \( V \) is called an \({equivalence\; set}\) if every component of the induced subgraph \( (S) \) is complete. In this paper, starting with the concept of equivalence set as a seed property, we form an inequality chain of six parameters, which we call the \({equivalence\; chain}\) of \( G \). We present several basic results on these parameters and problems for further investigation.

It has been known for some time that the Higman-Sims graph can be decomposed into the disjoint union of two Hoffman-Singleton graphs. In this paper, we establish that the Higman-Sims graph can be edge decomposed into the disjoint union of 5 double-Petersen graphs, each on 20 vertices. It is shown that, in fact, this can be achieved in 36,960 distinct ways. It is also shown that these different ways fall into a single orbit under the automorphism group \(\text{HS}\) of the graph.

Recently, Graves, Pisanski, and Watkins have determined the growth rates of Bilinski diagrams of one-ended, 3-connected, edge-transitive planar maps. The computation depends solely on the edge-symbol \((p,q;k,l)\) that was introduced by B. Gr\”unbaum and G. C. Shephard in their classification of such planar tessellations. We present a census of such tessellations in which we describe some of their properties, such as whether the edge-transitive planar tessellation is vertex- or face-transitive, self-dual, bipartite, or Eulerian. In particular, we order such tessellations according to the growth rate and count the number of tessellations in each subclass.

We give general lower bounds and upper bounds on the maximum degree \(\Delta(G)\) of a \(3_t\)-critical graph \(G\) in terms of the order of \(G\). We also establish tighter sharp lower bounds on \(\Delta(G)\) in terms of the order of \(G\) for several families of \(3_t\)-critical graphs, such as crown-graphs, claw-free graphs, and graphs with independence number \(\alpha(G) = 2\).

We simplify and further develop the methods and ideas of [A. Gagarin, W. Kocay, “Embedding graphs containing \( K_5 \)-subdivisions,” Ars Combin. 64 (2002), pp. 33-49] to efficiently test embeddability of graphs on the torus. Given a non-planar graph \( G \) containing a \( K_5 \)-subdivision subgraph, we show that it is possible either to transform the \( K_5 \)-subdivision into a certain type of \( K_{3,3} \)-subdivision, or else to reduce the toroidality testing problem for \( G \) to a small constant number of planarity checks and, eventually, rearrangements of planar embeddings. It is shown how to consider efficiently only one \( K_5 \)-subdivision in the input graph \( G \) to decide whether \( G \) is embeddable on the torus. This makes it possible to detect a bigger class of toroidal and non-toroidal graphs.

A graph \( G \) is called rainbow with respect to an edge coloring if no two edges of \( G \) have the same color. Given a host graph \( H \) and a guest graph \( G \subseteq H \), an edge coloring of \( H \) is called \( G \)-anti-Ramsey if no subgraph of \( H \) isomorphic to \( G \) is rainbow. The anti-Ramsey number \( f(H, G) \) is the maximum number of colors for which there is a \( G \)-anti-Ramsey edge coloring of \( H \). In this note, we consider cube graphs \( Q_n \) as host graphs and cycles \( C_k \) as guest graphs. We prove some general bounds for \( f(Q_n, C_k) \) and give the exact values for \( n \leq 4 \).