Let $k$ and $\ell$ be nonnegative integers, not both zero, and $D\subseteq N–\{1\}$. A (connected) graph $G$ is defined to be $(k,\ell ,D)$-stable if for every pair $u,v$ of vertices of $G$ with $d_G(u,v)\in D$ and every set $S$ consisting of at most $k$ vertices of $V(G)–\{u,v\}$ and at most $\ell$ edges of $E(G)$, the distance between $u$ and $v$ in $G–S$ equals $d_G(u,v)$. For a positive integer $m$, let $N_{\ge m}=\{x\in N\mid x\ge m\}$. It is shown that a graph is $(k,\ell ,\{m\})$-stable if and only if it is $(k,\ell ,N_{\ge m})$-stable. Further, it is established that for every positive integer $x$, a graph is $(k+x,\ell ,\{2\})$-stable if and only if it is $(k,\ell +x,\{2\})$-stable. A generalization of $(k,\ell ,\{m\})$-stable graphs is considered. For a planar $(k,0,\{m\})$-stable graph, $m\ge 3$, a sharp bound for $k$ in terms of $m$ is derived.

Given a graph $G$ with weighting $w:E(G)\to Z^{+}$, the strength of $G(w)$ is the maximum weight on any edge. The sum of a vertex in $G(w)$ is the sum of the weights of all its incident edges. $G(w)$ is $irregular$ if the vertex sums are distinct. The $irregularitystrength$ of a graph is the minimum strength of the graph under all irregular weightings. We present fast heuristic algorithms, based on hill-climbing and simulated annealing, for finding irregular weightings of a given strength. The heuristics are compared empirically, and the algorithms are then used to formulate a conjecture.

A graph $G$ is said to be maximal clique irreducible if each maximal clique in $G$ contains an edge which is not contained in any other maximal clique of $G$. In 1981, Opsut and Roberts proved that any interval graph is maximal clique irreducible. In this paper, we generalize their result and consider the question of characterizing maximal clique irreducible graphs.

It is shown that the obvious necessary condition $\lambda h(h–1)m^2\equiv 0(\mathrm{mod}k)$ for the existence of a $(v,k,\lambda )$-perfect Mendelsohn design with $h$ holes of size $m$ is sufficient in the case of block size three, except for a nonexisting $(6,3,1)$-PMD.

We introduce neighborhood intersection graphs and multigraphs of loop-graphs to generalize the standard notions of square and distance-two graphs. These neighborhood (multi)graphs are then used to construct self-dual graphs and multigraphs (embedded on surfaces of varying genus) which have involutory vertex-face mappings.

As stated in $[2]$, there is a conjecture that the determinant function maps the set of $n\times n$ $(0,1)$-matrices onto a set of consecutive integers for any given $n$. While this is true for $n\le 6$, it is shown to be false for $n=7$. In particular, there is no $7\times 7$ determinant in the range $28–31$, but there is one equal to $32$. Then the more general question of the range of the determinant function for all $n$ is discussed. A lower bound is given on the largest string of consecutive integers centered at $0$, each of which is a determinant of an $n\times n$ $(0,1)$-matrix.

In this paper, we prove that for any even integer $m\ge 4$, there exists a nested $m$-cycle system of order $n$ if and only if $n\equiv 1\mathrm{mod}2m$, with at most $13$ possible exceptions (for each value of $m$). The proof depends on the existence of certain group-divisible designs that are of independent interest. We show that there is a group-divisible design having block sizes from the set $\{5,9,13,17,29,49\}$, and having $u$ groups of size $4$, for all $u\ge 5$, $u\ne 7,8,12,14,18,19,23,24,33,34$.

We give a general construction of a triangle-free graph on $4p$ points whose complement does not contain $K_{p+2}–e$ for $p\ge 4$. This implies that the Ramsey number $R(K_3,K_k–e)\ge 4k–7$ for $k\ge 6$. We also present a cyclic triangle-free graph on $30$ points whose complement does not contain $K_9–e$. The first construction gives lower bounds equal to the exact values of the corresponding Ramsey numbers for $k=6,7,$ and $8$. The upper bounds are obtained by using computer algorithms. In particular, we obtain two new values of Ramsey numbers $R(K_3,K_8–e)=25$ and $R(K_3,K_9–e)=31$, the bounds $36\le R(K_3,K_{10}–e)\le 39$, and the uniqueness of extremal graphs for Ramsey numbers $R(K_3,K_6–e)$ and $R(K_3,K_7–e)$.

The concept of ladder tableaux is introduced, which may be considered as a natural extension of the shifted tableaux. By means of the dominance technique, a pair of determinantal expressions in terms of symmetric functions, for the generating function of ladder tableaux with a fixed shape, is established. As applications, the particular cases yield the generating functions for column-strict reverse plane partitions, symmetrical reverse plane partitions, and column-strict shifted reverse plane partitions with a given shape and with no part-restrictions.

Gyárfás and Lehel conjectured that any collection of trees $T_2,T_3,\dots ,T_n$ on $2,3,\dots ,n$ vertices respectively, can be packed into the complete graph on $n$ vertices. Fishburn proved that the conjecture is true for some classes of trees and for all trees up to $n=9$. Pritikin characterized the trees for which Fishburn’s proof works and extended the classes of trees for which the conjecture is known to be true. Using a computer, we have shown that the conjecture is true through $n=11$, but also that an approach suggested by Fishburn is unlikely to work in general.

The $dominationnumber$ $\gamma (G)$ of a graph $G=(V,E)$ is the smallest cardinality of a $dominating$ set $X$ of $G$, i.e., of a subset $X$ of vertices such that each $v\in V–X$ is adjacent to at least one vertex of $X$. The $k$-$minimaldominationnumber$ ${\mathrm{\Gamma }}_k(G)$ is the largest cardinality of a dominating set $Y$ which has the following additional property: For every $\ell$-subset $Z$ of $Y$ where $\ell \le k$, and each $(\ell -1)$-subset $W$ of $V–Y$, the set $(Y–Z)\cup W$ is not dominating. In this paper, for any positive integer $k\ge 2$, we exhibit self-complementary graphs $G$ with $\gamma (G)>k$ and use this and a method of Graham and Spencer to construct $n$-vertex graphs $F$ for which ${\mathrm{\Gamma }}_k(F){\mathrm{\Gamma }}_k(\overline{F})>n$.

In this paper, simple $2-(9,4,\lambda )$ designs are constructed for $\lambda =3q$, $1\le q\le 7$, and indecomposable simple $2-(v,k,\lambda )$ designs are constructed for all $10\le v\le 16$ and the smallest possible $\lambda$ for which the existence of simple $2-(v,k,\lambda )$ designs was previously undecided.

We prove that for every $v\equiv 4,8(\mathrm{mod}12)$ with $v\ge 16$, there exists a pair of $S(3,4,v)$s having exactly $k\in \{0,1,\dots ,\lfloor \frac{v}{4}\rfloor \}$ pairwise disjoint blocks in common.

Numbers similar to those of van der Waerden are examined by considering sequences of positive integers $\{x_1,x_2,\dots ,x_n\}$ with $x_{i+1}=x_i+d+r_i$, where $d\in Z^{+}$ and $0\le r_i\le max(0,f(i))$ for a given function $f$ defined on $Z^{+}$. Let $w_f(n)$ denote the least positive integer such that if $\{1,2,\dots ,w_f(n)\}$ is $2$-colored, then there exists a monochromatic sequence of the type just described. Tables are given of $w_f(n)$ where $f(i)=i–k$ for various constants $k$, and also where $f(i)=i$ if $i\ge 2$, $f(1)=0$. In this latter case, as well as for $f(i)=i$, an upper bound is given that is very close to the actual values. A tight lower bound and fairly reasonable upper bound are given in the case $f(i)=i–1$.

It is also shown that for a certain family of graphs (called thistles), the coefficients of the matching polynomial repeat themselves symmetrically. This turns out to be a characterizing property for some thistles.

It is shown that the basis graphs of every family of circulants are characterized by their matching polynomials. Explicit formulas are also given for their matching polynomials. From these results, the analogous formulas for the chromatic polynomials of the complements of the basis graphs, are obtained. It is shown that a basis graph of a family of circulants is chromatically unique if and only if it is connected. Also, some interesting results of a computer investigation are discussed and conjectures are made.

In this paper, we introduce the concept of similar graphs. Similar graphs arise in the design of fault-tolerant networks and in load balancing of the networks in case of node failures. Similar graphs model networks that not only remain connected but also allow a job to be shifted to other processors without re-executing the entire job. This dynamic load balancing capability ensures minimal interruption to the network in case of single or multiple node failures and increases overall efficiency. We define a graph to be $(m,n)$-similar if each vertex is contained in a set of at least $m$ vertices, each pair of which share at least $n$ neighbors. Several well-known classes of $(2,2)$-similar graphs are characterized, for example, triangulated, comparability, and co-comparability. The problem of finding a minimum augmentation to obtain a $(2,2)$-similar graph is shown to be NP-Complete. A graph is called strongly $m$-similar if each vertex is contained in a set of at least $m$ vertices with the property that they all share the same neighbors. The class of strongly $m$-similar graphs is completely characterized.

A star $S_q$, with $q$ edges, is a complete bipartite graph $K_{1,q}$. Two figures of the complete graph $K_n$ on a given set of $k$ vertices are compatible if they are edge-disjoint, and a configuration is a set of pairwise compatible figures. In this paper, we take stars as our figures. A configuration $C$ is said to be maximal if there is no figure (star) $f\notin C$ such that $\{f\}\cup C$ is also a configuration. The size of a configuration $F$, denoted by $|F|$, is the number of its figures. Let $\text{Spec}(n,q)$ (or simply $\text{Spec}(n)$) denote the set of all sizes such that there exists a maximal configuration of stars with this size. In this paper, we completely determine $\text{Spec}(n)$, the spectrum of maximal configurations of stars. As a special case, when $n$ is an order of a star system, we obtain the spectrum of maximal partial star systems.

It is proved in this paper that for $\lambda =4$ and $5$, the necessary conditions for the existence of a simple $B(4,\lambda ;v)$ are also sufficient. It is also proved that for $\lambda =4$ and $5$, the necessary conditions for the existence of an indecomposable simple $B(4,\lambda ;v)$ are also sufficient, with the unique exception $(v,\lambda )=(7,4)$ and $10$ possible exceptions.

Let $S$ and $T$ be sets with $|S|=m$ and $|T|=n$. Let $S_3,S_2$ and $T_3,T_2$ be the sets of all $3$-subsets ($2$-subsets) of $S$ and $T$, respectively. Define $Q((m,2,3),(n,2,3))$ as the smallest subset of $S_2\times T_2$ needed to cover all elements of $S_3\times T_3$. A more general version of this problem is initially defined, but the bulk of the investigation is devoted to studying this number. Its property as a lower bound for a planar crossing number is the reason for this focus.

Under some assumptions on the incidence matrices of symmetric designs, we prove a non-existence theorem for symmetric designs. The approach generalizes Wilbrink’s result on difference sets $[7]$.

In this paper, we derive some inequalities which the parameters of a two-symbol balanced array $T$ ($B$-array) of strength four must satisfy for $T$ to exist.

This paper considers Latin squares of order $n$ having $0,1,\dots ,n-1$ down the main diagonal and in which the back diagonal is a permutation of these symbols (diagonal squares). It is an open question whether or not such a square which is self-orthogonal (i.e., orthogonal to its transpose) exists for order $10$. We consider two possible constraints on the general concept: self-conjugate squares and strongly symmetric squares. We show that relative to each of these constraints, a corresponding self-orthogonal diagonal Latin square of order $10$ does not exist. However, it is easy to construct self-orthogonal diagonal Latin squares of orders $8$ and $12$ which satisfy each of the constraints respectively.