Kahn (see [3]) reported that N. Alon, M. Saks, and P. D. Seymour made the following conjecture. If the edge set of a graph \(G\) is the disjoint union of the edge sets of \(m\) complete bipartite graphs, then \(\chi(G) \leq m+1\). The purpose of this paper is to provide a proof of this conjecture for \(m \leq 4\) and \(m \geq n – 3\) where \(G\) has \(n\) vertices.

A graph \(G(V, E)\) is a mod sum graph if there is a labeling of the vertices with distinct positive integers so that an edge is present if and only if the sum of the labels of the vertices incident on the edge, modulo some positive integer, is the label of a vertex of the graph. It is known that wheels are not mod sum graphs. The mod sum number of a graph is the minimum number of isolates that, together with the given graph, form a mod sum graph. The mod sum number is known for just a few classes of graphs. In this paper we show that the mod sum number of the \(n\)-spoked wheel, \(\rho(W_n)\), \(n \geq 5\), is \(n\) when \(n\) is odd and \(2\) when \(n\) is even.

De Bruijn sequences had been well investigated in \(70s-80s\). In the past, most of the approaches used to generate de Bruijn sequences were based upon either finite field theory or combinatorial theory. This paper describes a simple approach for generating de Bruijn sequences as “seeds”, and then based upon the “seeds”, a simple procedure is presented to reproduce a class of de Bruijn sequences. Numerical results of the distribution of reproduced sequences are provided. Additionally, this paper also reports some recent applications of de Bruijn sequences in psychology and engineering.

In a graph \(G = (V, E)\), a set \(S\) of vertices (as well as the subgraph induced by \(S\)) is said to be dominating if every vertex in \(V \setminus S\) has at least one neighbor in \(S\). For a given class \(\mathcal{D}\) of connected graphs, it is an interesting problem to characterize the class \({Dom}(\mathcal{D})\) of graphs \(G\) such that each connected induced subgraph of \(G\) contains a dominating subgraph belonging to \(\mathcal{D}\). Here we determine \({Dom}(\mathcal{D})\) for \(\mathcal{D} = \{P_1, P_2, P_5\}\), \(\mathcal{D} = \{K_t \mid t \geq 1\} \cup \{P_5\}\), and \(\mathcal{D} =\) {connected graphs on at most four vertices} (where \(P_t\) and \(K_t\) denote the path and the complete graph on \(t\) vertices, respectively). The third theorem solves a problem raised by Cozzens and Kelleher [\(Discr. Math.\) 86 (1990), 101-116]. It turns out that, in each case, a concise characterization in terms of forbidden induced subgraphs can be given.

We use the results on \(5\)-GDDs to obtain optimal packings with block size five and index one. In particular, we prove that if \(v \equiv 2, 6, 10 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with at most \(32\) possible exceptions. Furthermore, if \(v \equiv 14, 18 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with a finite (large) number of possible exceptions.

A chromatic root is a root of the chromatic polynomial of some graph \(G\). E. Farrell conjectured in \(1980\) that no chromatic root can lie in the left-half plane, and in \(1991\) Read and Royle showed by direct computation that the chromatic polynomials of some graphs do have a root there. These examples, though, yield only finitely many such chromatic roots. Subsequent results by Shrock and Tsang show the existence of chromatic roots of arbitrarily large negative real part. We show that theta graphs with equal path lengths of size at least \(8\) have chromatic roots with negative real part.

The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.

The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).

We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.

We introduce the notion of premature partial Latin squares; these cannot be completed, but if any of the entries is deleted, a completion is possible. We study their spectrum, i.e., the set of integers \(t\) such that there exists a premature partial Latin square of order \(n\) with exactly \(t\) nonempty cells.