It was conjectured by Paul Erdős that if \(G\) is a graph with chromatic number at least \(k\), then the diagonal Ramsey number \(r(G) \geq r(K_k)\). That is, the complete graph \(K_k\) has the smallest diagonal Ramsey number among the graphs of chromatic number \(k\). This conjecture is shown to be false for \(k = 4\) by verifying that \(r(W_6) = 17\), where \(W_6\) is the wheel with \(6\) vertices, since it is well known that \(r(K_4) = 18\). Computational techniques are used to determine \(r(W_6)\) as well as the Ramsey numbers for other pairs of small order wheels.

A simple model of an unreliable network is a probabilistic graph in which each edge has an independent probability of being operational. The two-terminal reliability is the probability that specified source and target nodes are connected by a path of operating edges.
Upper bounds on the two-terminal reliability can be obtained from an edge-packing of the graph by source-target cutsets. However, the particular cutsets chosen can greatly affect the bound.
In this paper, we examine three cutset selection strategies, one of which is based on a transshipment formulation of the \(k\)-cut problem.
These cutset selection strategies allow heuristics for obtaining good upper bounds analogous to the pathset selection heuristics used for lower bounds.
The computational results for some example graphs from the literature provide insight for obtaining good edge-packing bounds. In particular, the computational results indicate that, for the purposes of generating good reliability bounds, the effect of allowing crossing cuts cannot be ignored, and should be incorporated in a good edge-packing heuristic.
This gives rise to the problem of finding a least cost cutset whose contraction in the graph reduces the source-target distance by exactly one.

Chvátal conjectured that if \(G\) is a \(k\)-tough graph and \(k|V(G)|\) is even, then \(G\) has a \(k\)-factor. In \([5\) it was proved that Chvátal’s conjecture is true. Katerinis\([2]\) presented a toughness condition for a graph to have an \([a, b]\)-factor. In this paper, we prove a stronger result: every \((a – 1 + a/b)\)-tough graph satisfying all necessary conditions has an \([a, b]\)-factor containing any given edge and another \([a, b]\)-factor excluding it. We also discuss some special cases of the above result.

R.A. Bailey has conjectured that all finite groups except elementary Abelian \(2\)-groups with more than one factor have \(2\)-sequencings (i.e., terraces). She verified this for all groups of order \(n\), \(n \leq 9\). Results proved since the appearance of Bailey’s paper make it possible to raise this bound to \(n \leq 87\) with \(n = 64\) omitted. Relatively few groups of order not \(2^n\), \(n \in \{4, 5\}\) must be handled by machine computation.

A set \(S\) of vertices of a graph \(G = (V, E)\) is a global dominating set if \(S\) dominates both \(G\) and its complement \(\overline{G}\). The concept of global domination was first introduced by Sampathkumar. In this paper, we extend this notion to irredundancy. A set \(S\) of vertices will be called universal irredundant if \(S\) is irredundant in both \(G\) and \(\overline{G}\). A set \(S\) will be called global irredundant if for every \(x\) in \(S\), \(x\) is an irredundant vertex in \(S\) either in \(G\) or in \(\overline{G}\). We investigate the universal irredundance and global irredundance parameters of a graph. It is also shown that the determination of the upper universal irredundance number of graphs is NP-Complete.

We enumerate by computer algorithms all simple \(t-(t+7, t+1, 2)\) designs for \(1 \leq t \leq 5\), i.e., for all possible \(t\). This enumeration is new for \(t \geq 3\). The number of nonisomorphic designs is equal to \(3, 13, 27, 1\) and \(1\) for \(t = 1, 2, 3, 4\) and \(5\), respectively. We also present some properties of these designs, including orders of their full automorphism groups and resolvability.

Let \(G\) be a finite simple graph. The vertex clique covering number \({vcc}(G)\) of \(G\) is the smallest number of cliques (complete subgraphs) needed to cover the vertex set of \(G\). In this paper, we study the function \({vcc}(G)\) for the case when \(G\) is \(r\)-regular and \((r-2)\)-edge-connected. A sharp upper bound for \({vcc}(G)\) is determined. Further, the set of possible values of \({vcc}(G)\) when \(G\) is a \(4\)-regular connected graph is determined.

We consider certain resolvable designs which have applications to doubly perfect Cartesian authentication schemes. These generalize structures determined by sets of mutually orthogonal Latin squares and are related to semi-Latin squares and other designs which find applications in the design of experiments.