The binding number of a graph \(G\) is defined to be the minimum of \(|N(S)|/|S|\) taken over all nonempty \(S \subseteq V(G)\) such that \(N(S) \neq V(G)\). In this paper, another look is taken at the basic properties of the binding number. Several bounds are established, including ones linking the binding number of a tree to the “distribution” of its end-vertices. Further, it is established that under some simple conditions, \(K_{1,3}\)-free graphs have binding number equal to \((p(G) – 1)/(p(G) – \delta(G))\) and applications of this are considered.

Strongly regular graphs are graphs in which every adjacent pair of vertices share \(\lambda\) common neighbours and every non-adjacent pair share \(\mu\) common neighbours. We are interested in strongly regular graphs with \(\lambda = \mu = k\) such that every such set of \(k\) vertices common to any pair always induces a subgraph with a constant number \(x\) of edges. The Friendship Theorem proves that there are no such graphs when \(\lambda = \mu = 1\). We derive constraints which such graphs must satisfy in general, when \(\lambda = \mu > 1\), and \(x \geq 0\), and we find the set of all parameters satisfying the constraints. The result is an infinite, but sparse, collection of parameter sets. The smallest parameter set for which a graph may exist has \(4896\) vertices, with \(k = 1870\).

The idea of a domino square was first introduced by J. A. Edwards et al. in [1]. In the same paper, they posed some problems on this topic. One problem was to find a general construction for a whim domino square of side \(n \equiv 3 \pmod{4}\). In this paper, we solve this problem by using a direct construction. It follows that a whim domino square exists for each odd side [1].

It is shown, through an exhaustive search, that there are no circulant symmetric Williamson matrices of order \(39\). The construction of symmetric but not circulant Williamson-type matrices of order \(39\), first given by Miyamoto, Seberry and Yamada, is given explicitly.

A graph \(G\) is defined by Chvátal \([4]\) to be \(n\) \({tough}\) if, given any set of vertices \(S, S \subseteq G\), \(c(G – S) \leq \frac{|S|}{n}\). We present several results relating to the recognition and construction of \(1\)-tough graphs, including the demonstration that all \(n\)-regular, \(n\)-connected graphs are \(1\)-tough. We introduce the notion of minimal \(1\)-tough graphs, and tough graph augmentation, and present results relating to these topics.

The integrity of a graph \(G\), denoted \(I(G)\), is defined by \(I(G) = \min\{|S| + m(G – S) : S \subset V(G)\}\) where \(m(G – S)\) denotes the maximum order of a component of \(G – S\); further an \(I\)-set of \(G\) is any set \(S\) for which the minimum is attained. Firstly some useful concepts are formalised and basic properties of integrity and \(I\)-sets identified. Then various bounds and interrelationships involving integrity and other well-known graphical parameters are considered, and another formulation introduced from which further bounds are derived. The paper concludes with several results on the integrity of circulants.

The new concept of \(M\)-structures is used to unify and generalize a number of concepts in Hadamard matrices, including Williamson matrices, Goethals-Seidel matrices, Wallis-Whiteman matrices, and generalized quaternion matrices. The concept is used to find many new symmetric Williamson-type matrices, both in sets of four and eight, and many new Hadamard matrices. We give as corollaries “that the existence of Hadamard matrices of orders \(4g\) and \(4h\) implies the existence of an Hadamard matrix of order \(8gh\)” and “the existence of Williamson type matrices of orders \(u\) and \(v\) implies the existence of Williamson type matrices of order \(2uv\)”. This work generalizes and utilizes the work of Masahiko Miyamoto and Mieko Yamada.

Consider \(n\) bridge teams each consisting of two pairs (the two pairs are called \({teammates}\)). A match is a triple \((i, j, b)\) where pair \(i\) opposes pair \(j\) on a board \(b\); here \(i\) and \(j\) are not teammates and “oppose” is an ordered relation. The problem is to schedule a tournament for the \(n\) teams satisfying the following conditions with a minimum number of boards:

1. Every pair must play against every other pair not on its team exactly once.
2. Every pair must play one match at every round.
3. Every pair must play every board exactly once except for odd \(n\), each pair can skip a board.
4. If pair \(i\) opposes pair \(j\) on a board, then the teammate of \(j\) must oppose the teammate of \(i\) on the same board.
5. Every board is played in at most one match at a round.

We call a schedule satisfying the above five conditions a \({complete \; coupling \; round \; robin \; schedule}\) (CCRRS) and one satisfying the first four conditions a \({coupling \; round \; robin \; schedule}\) (CRRS). While the construction of CCRRS is a difficult combinatorial problem, we construct CRRS for every \(n \geq 2\).

The concept of using basis reduction for finding \(t–(v,k,\lambda)\) designs without repeated blocks was introduced by D. L. Kreher and S. P. Radziszowski at the Seventeenth Southeastern International Conference on Combinatorics, Graph Theory and Computing. This tool and other algorithms were packaged into a system of programs that was called the design theory toolchest. It was distributed to several researchers at different institutions. This paper reports the many new open parameter situations that were settled using this toolchest.

We consider a generalization of the well-known gossip problem: Let the information of each point of a set \(X\) be conveyed to each point of a set \(Y\) by \(k\)-party conference calls. These calls are organized step-wisely, such that each point takes part in at most one call per step. During a call all the \(k\) participants exchange all the information they already know. We investigate the mutual dependence of the number \(L\) of calls and the number \(T\) of steps of such an information exchange. At first a general lower bound for \(L.k^T\) is proved. For the case that \(X\) and \(Y\) equal the set of all participants, we give lower bounds for \(L\) or \(T\), if \(T\) resp. \(L\) is as small as possible. Using these results the existence of information exchanges with minimum \(L\) and \(T\) is investigated. For \(k = 2\) we prove that for even \(n\), there is one of this kind if \(n \leq 8\).