In this paper, we characterize the potentially \(C_k\)-graphic sequence for \(k = 3, 4, 5\). These characterizations imply several theorems due to P. Erdős, M. S. Jacobson, and J. Lehel [1], R. J. Gould, M. S. Jacobson, and J. Lehel [2], and C. H. Lai [5] and [6], respectively.

Bailey, Cheng, and Kipnis [3] developed a method for constructing trend-free run orders of factorial experiments called the generalized fold-over method (GFM). In this paper, we use the GFM of constructing run orders of factorial experiments to give a systematic method of constructing magic squares of higher order.

In this paper, we focus on the identification of Latin interchanges in Latin squares that are the direct product of Latin squares of smaller orders. The results we obtain on Latin interchanges will be used to identify critical sets in direct products. This work is an extension of research carried out by Stinson and van Rees in \(1982\).

A \((g,k; \lambda)\)-difference matrix over the group \((G, o)\) of order \(g\) is a \(k\) by \(g\lambda\) matrix \(D = (d_{ij})\) with entries from \(G\) such that for each \(1 \leq i < j \leq k\), the multiset \(\{d_{il}\) o \(d_{jl}^{-1} \mid 1 \leq l \leq g\lambda\}\) contains every element of \(G\) exactly \(\lambda\) times. Some known results on the non-existence of generalized Hadamard matrices, i.e., \((g,g\lambda; \lambda)\)-difference matrices, are extended to \((g, g-1; \lambda)\)-difference matrices.

The notion of convexity in graphs is based on the one in topology: a set of vertices \(S\) is convex if an interval is entirely contained in \(S\) when its endpoints belong to \(S\). The order of the largest proper convex subset of a graph \(G\) is called the convexity number of the graph and is denoted \(con(G)\). A graph containing a convex subset of one order need not contain convex subsets of all smaller orders. If \(G\) has convex subsets of order \(m\) for all \(1 \leq m \leq con(G)\), then \(G\) is called polyconvex. In response to a question of Chartrand and Zhang [3], we show that, given any pair of integers \(n\) and \(k\) with \(2 \leq k < n\), there is a connected triangle-free polyconvex graph \(G\) of order \(n\) with convexity number \(k\).

In this work, \(\Gamma\) denotes a finite, simple, and connected graph. The \(k\)-excess \(e_k(H)\) of a set \(H \subseteq V(\Gamma)\) is defined as the cardinality of the set of vertices that are at distance greater than \(k\) from \(H\), and the \(k\)-excess \(e_k(h)\) of all \(A\)-subsets of vertices is defined as

\[e_k(h) = \max_{H \subset V(\Gamma),|H|=h} \{ e_k(H) \}\]

The \(k\)-excess \(e_k\) of the graph is obtained from \(e_k(h)\) when \(h = 1\). Here we obtain upper bounds for \(e_k(h)\) and \(e_k\) in terms of the Laplacian eigenvalues of \(\Gamma\).

Let \(G\) be a \(k\)-connected graph and let \(F\) be the simple graph obtained from \(G\) by removing the edge \(xy\) and identifying \(x\) and \(y\) in such a way that the resulting vertex is incident to all those edges (other than \(xy\)) which are originally incident to \(x\) or \(y\). We say that \(e\) is contractible if \(F\) is \(k\)-connected. A bowtie is the graph consisting of two triangles with exactly one vertex in common. We prove that if a \(k\)-connected graph \(G\) (\(k \geq 4\)) has no contractible edge, then there exists a bowtie in \(G\).

We prove that the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+3}\) is at least \(2n\) less than the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+2}\), where \(n\) is a nonnegative integer. Harary explicitly gave all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_6\). In this paper, we give all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_7\).

We restate a recent improvement of the inclusion-exclusion principle in terms of valuations on distributive lattices and present a completely new proof of the result. Moreover, we establish set-theoretic identities and logical equivalences of inclusion-exclusion type, which have not been considered before.

Let \(\delta(G)\) denote the minimum degree of a graph \(G\). We prove that for \(t \geq 4\) and \(k \geq 2\), a graph \(G\) of order at least \((t + 1)k + 2t^2 – 4t + 2\) with \(\delta(G) \geq k+t- 1\) contains \(k\) pairwise vertex-disjoint \(K_{1,t}\)’s.

In this paper, we construct a squag \(SQG(3n)\) of cardinality \(3n\) that contains three given arbitrary squags \(SQG(n)\)s as disjoint subquags. Accordingly, we can construct a subdirectly irreducible squag \(SQG(3n)\), for each \(n \geq 7\), with \(n \equiv 0, 3 \pmod{6}\). Also, we want to review the shape of the congruence lattice of non-simple squags \(SQG(n)\) for some \(n\) and to give a classification of the class of all \(SQG(21)\)s and the class of all \(SQG(27)\)s according to the shape of its congruence lattice. \(SQG(21)\)s are classified into three classes and \(SQG(27)\)s are classified into four classes. The construction of \(SQG(3n)\), which is given in this paper, helps us to construct examples of each class of both \(SQG(21)\)s and \(SQG(27)\)s.

We show how to produce algebraically a complete orthogonal set of Latin squares from a left quasifield and how to generate algebraically a maximal set of self-orthogonal Latin squares from a left nearfield.

A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k; g)\)-cage is a \((k; g)\)-graph with the least possible number of vertices. In this paper, we prove that all \((4; g)\)-cages are \(4\)-connected, a special case of the conjecture about \((k; g)\)-cages’ connectivity made by H.L. Fu \(et\; al [1]\).

A set \(S\) of vertices of a graph \(G\) is a total dominating set if every vertex of \(V(G)\) is adjacent to some vertex in \(S\). The total domination number \(\gamma_t(G)\) is the minimum cardinality of a total dominating set of \(G\). 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}\). The graph \(G\) is \(k\)-critical relative to \(K_{s,s}\) if \(\gamma_t(G) = k\) and \(\gamma_t(G + e) < k\) for all \(e \in E(H)\). We study \(k_t\)-critical graphs relative to \(K_{s,s}\) for small values of \(k\). In particular, we characterize the \(3\)-critical and \(4_t\)-critical graphs.

Let \(S\) be a nonempty subset of the cyclic group \(\mathbb{Z}_p\), where \(p\) is an odd prime. Denote the \(n\)-fold sum of \(S\) as \(n..S\). That is,\(n..S = \{s_1 + \cdots + s_n \mid s_1, \ldots, s_n \in S\}.\) We say that \(S\) is an \((n, 0)\)-set if \(0 \notin n..S\). Let \(k, s\) be integers with \(k \geq 2\) such that \(p-1 = ks\). In this paper, we determine the number of \((k, 0)\)-sets of \(\mathbb{Z}_p\) which are in arithmetic progression and show explicitly the forms taken by those \((k, 0)\)-sets which achieve the maximum cardinality.

In this paper, necessary and sufficient conditions are given for the existence of extended \(5\)-cycle systems of order \(n\) which have \(r\) idempotent elements.

An \((f,2)\)-graph is a multigraph \(G\) such that each vertex of \(G\) has degree either \(f\) or \(2\). Let \(S(n, f)\) denote the simple graph whose vertex set is the set of unlabeled \((f,2)\)-graphs of order no greater than \(n\) and such that \(\{G, H\}\) is an edge in \(S(n, f)\) if and only if \(H\) can be obtained from \(G\) by either an insertion or a suppression of a vertex of degree \(2\). We also consider digraphs whose nodes are labeled or unlabeled \((f, 2)\)-multigraphs and with arcs \((G, H)\) defined as for \(\{G, H\}\).

We study the structure of these graphs and digraphs. In particular, the diameter of a given component is determined. We conclude by defining a random process on these digraphs and derive some properties. Chemistry applications are suggested.

Given a coloring \(f\) of Euclidean space \(\mathbb{R}^n\) and some group \(G\) of its transformations, its subsets \(A\) and \(B\) are said to be colored similarly, if there exists \(g \in G\), such that \(B = g(A)\) and \(f(a) = f(g(a))\), for all \(a \in A\). From our earlier result [12] it follows that there are \(2\)-colorings of \(\mathbb{R}^n\), in which no two different line segments are colored similarly with respect to isometries. The main purpose of this paper is to investigate other types of such pattern avoiding colorings. In particular, we consider topological as well as measure theoretic aspects of the above scene. Our motivation for studying this topic is twofold. One is that it extends square-free colorings of \(\mathbb{R}\), introduced in [2] as a continuous version of the famous non-repetitive sequences of Thue. The other is its relationship to some exciting problems and results of Euclidean Ramsey Theory, especially those concerning avoiding distances.

In this paper, a definition of perfect binary matroids is considered and it is shown that, analogous to the Perfect Graph Theorem of Lovász and Fulkerson, the complement of a perfect matroid is also a perfect matroid. In addition, the classes of critically imperfect graphic matroids and critically imperfect graphs are compared.

A \((p,q)\) graph \(G\) is edge-magic if there exists a bijective function \(f : V(G) \cup E(G) \to \{1,2,\ldots,p+q\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant, called the valence of \(f\), for any edge \(uv\) of \(G\). Moreover, \(G\) is said to be super edge-magic if \(f(V(G)) = \{1,2,\ldots,p\}\). Every super edge-magic \((p,q)\) graph is cordial, and it is harmonious and sequential whenever it is a tree or \(q \geq p\). In this paper, it is shown to be edge-antimagic as well. The super edge-magic properties of several classes of connected and disconnected graphs are studied. Furthermore, we prove that there can be arbitrarily large gaps among the possible valences for certain super edge-magic graphs. We also establish that the disjoint union of multiple copies of a super edge-magic linear forest is super edge-magic if the number of copies is odd.

In this paper, necessary and sufficient conditions are given for the metamorphosis of a \(\lambda\)-fold \(K_{3,3}\)-design of order \(n\) into a \(\lambda\)-fold \(6\)-cycle system of order \(n\), by retaining one \(6\)-cycle subgraph from each copy of \(K_{3,3}\), and then rearranging the set of all the remaining edges, three from each \(K_{3,3}\), into further \(6\)-cycles so that the result is a \(\lambda\)-fold \(6\)-cycle system.

Partially balanced diallel cross block designs with \(m\) associate classes are defined and two general methods of construction are presented. Two-associate class designs based upon group divisible, triangular, and extended group divisible association schemes obtained using the general methods are also given. Tables of designs for no more than \(24\) parental lines are provided.

Given a non-planar graph \(G\) with a subdivision of \(K_5\) as a subgraph, we can either transform the \(K_5\)-subdivision into a \(K_{3,3}\)-subdivision if it is possible, or else we obtain a partition of the vertices of \(G\backslash K_5\) into equivalence classes. As a result, we can reduce a projective planarity or toroidality algorithm to a small constant number of simple planarity checks [6] or to a \(K_{3,3}\)-subdivision in the graph \(G\). It significantly simplifies algorithms presented in [7], [10], and [12]. We then need to consider only the embeddings on the given surface of a \(K_{3,3}\)-subdivision, which are much less numerous than those of \(K_5\).

Let \(M(d,n)\) denote the minimax number of group tests required for the identification of the \(d\) defectives in a set of \(n\) items. It was conjectured by Hu, Hwang, and Wang that \(M(d,n) = n-1\) for \(n \leq 3d\), a surprisingly difficult combinatorial problem with very little known. The best known result is \(M(d,n) = n-1\) for \(n \leq \frac{42}{16}d\) by Du and Hwang. In this note, we improve their result by proving \(M(d,n) = n – 1\) for \(d \geq 193\) and \(n \leq \frac{42}{16}d\).

In this paper, we investigate the divisibility of \(mn\) by \(am+bn+c\) for given \(a\), \(b\), and \(c\). We give the necessary and sufficient condition for the divisibility, that is, \(am + bn + c\) divides \(mn\). We then present the structure of the set of pairs \([m,n]\) that satisfies the divisibility. This structure is represented by a directed graph and we prove the necessary and sufficient condition for the graph to have a binary tree structure. In particular, for \(c = -1\), we show double binary tree structures on the set.