Numbers similar to those of van der Waerden are examined by considering sequences of positive integers \(\{x_1, x_2, \ldots, x_n\}\) with \(x_{i+1} = x_i + d + r_i\), where \(d \in {Z}^+\) and \(0 \leq r_i \leq \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, \ldots, 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 \geq 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.