Erdős and Gallai (1963) showed that any \(r\)-regular graph of order \(n\), with \(r < n-1\), has chromatic number at most \({3n}/{5}\), and this bound is achieved by precisely those graphs with complement equal to a disjoint union of 5-cycles.

We are able to generalize this result by considering the problem of determining a \((j-1)\)-regular graph \(G\) of minimum order \(f(j)\) such that the chromatic number of the complement of \(G\) exceeds \({f(j)}/{2}\). Such a graph will be called an \(F(j)\)-\({graph}\). We produce an \(F(j)\)-graph for all odd integers \(j \geq 3\) and show that \(f(j) = {5(j – 1)}/{2}\) if \(j \equiv 3 \pmod{4}\), and \(f(j) = 1 + {5(j – 1)}/{2}\) if \(j \equiv 1 \pmod{4}\).

A lemma of Enomoto, Llado, Nakamigawa and Ringel gives an upper bound for the edge number of a super edge-magic graph with \(p > 1\) vertices. In this paper we give some results which come out from answering some natural questions suggested by this useful lemma.

The scheme associated with a graph is an association scheme if and only if the graph is strongly regular. Consider the problem of extending such an association scheme to a superscheme in the case of a colored, directed graph. The obstacles can be expressed in terms of \(t\)-vertex conditions. If a graph does not satisfy the \(t\)-vertex condition, a prescheme associated with it cannot be erected beyond the \((t-3)\)rd-level.

A mandatory representation design MRD \((K; v)\) is a pairwise balanced design PBD \((K; v)\) in which for each \(k \in K\) there is at least one block in the design of size \(k\). The study of the mandatory representation designs is closely related to that of subdesigns in pairwise balanced designs. In this paper, we survey the known results on MRDs and pose some open questions.

It is shown that the necessary conditions are sufficient for the existence of all \(c\)-BRDs\((v, 3, \lambda)\) for negative \(c\)-values. This completes the study of \(c\)-BRDs with block size three as previously the authors and J. Seberry have shown that the necessary conditions are sufficient for \(c \geq -1\).

Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n-1\), \(G\) is \(k\)-\emph{extendable} if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \emph{strongly \(k\)-extendable} if \(G – \{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has been investigated only for the case \(k = 0\). In this paper, we focus on the problem of characterizing strongly \(k\)-extendable graphs for any \(k\). We present a number of properties of strongly \(k\)-extendable graphs including some necessary and sufficient conditions for strongly \(k\)-extendable graphs.

In this paper we count the number of non-homeomorphic continua in a certain collection of continua. The continua in these collections are trees with certain restrictions on them. We refer to a continuum in one of these collections as a caterpillar continuum.