We show that for each fixed \(k \geq 3\), the \({INDEPENDENT \; SET}\) problem is \(NP\)-complete for the class of \(k\)-regular graphs. Several other decision problems, including \({IRREDUNDANT \; SET}\), are also \(NP\)-complete for each class of \(k\)-regular graphs, for \(k \geq 6\).

For a positive integer \(d\), the usual \(d\)-dimensional cube \(Q_d\) is defined to be the graph \((K_2)^d\), the Cartesian product of \(d\) copies of \(K_2\). We define the generalized cube \(Q_{d,k}\) to be the graph \((K_k)^d\) for positive integers \(d\) and \(k\). We investigate the decompositions of the complete graph \(K_{k^d}\) and the complete \(k\)-partite graph \(K_{k \times k^{d-1}}\) into generalized cubes when \(k\) is the power of a prime and \(d\) is any positive integer, and some generalizations. We also use these results to show that \(Q_{5}\) divides \(K_{96}\).

We derive upper bounds for the number of edges in a triangle-free subgraph of a power of a cycle, extending results of an earlier paper by Bondy and Locke. In particular, the solution found for the case \(m = 20\) is a decomposition of \(3C^{20}_n\) into odd complete graphs.

The problem of maximizing the possible number of users of a packet radio network with time division multiplexing, when the number of slots per time frame and the maximum communication delay between users are given, can be modeled by a graph. In this paper, a new way of edge-coloring is presented on several families of large graphs on alphabets. This method allows us to obtain a certain improvement of the previous results.

An inductive process is used to find formulae for the number of 3-block configurations in BTD’s with parameters \((\mathcal{V}; \mathcal{B}; \mathcal{R}, p_1, p_2; 3; 2)\). In the process, a generating set of size nine is produced for the formulae. Because BIBD’s can be viewed as BTD’s with \(p_2 = 0\), once found, the BTD formulae yield the 3-block configuration formulae for BIBD’s with parameters \((v, b, r, 3, 2)\).

A directed triple system of order \(v\), denoted \(\text{DTS}(v)\), is said to be bicyclic if it admits an automorphism whose disjoint cyclic decomposition consists of two cycles. In this paper, we give necessary and sufficient conditions for the existence of bicyclic \(\text{DTS}(v)\)s.

The average distance in a connected weighted graph \(G\) is defined as the average of the distances between the vertices of \(G\). In 1985 P.M. Winkler [5] conjectured that every connected graph \(G\) contains an element \(e\), such that the removal of \(e\) enlarges the average distance by at most the factor \(\frac{4}{3}\).

D. Bienstock and E. Gyéri proved Winkler’s conjecture for the removal of an edge from a connected (unweighted) graph that has no vertices of degree one, and asked whether this conjecture holds for connected weighted graphs. In this paper we prove that any \(h\)-edge-connected weighted graph contains an edge whose removal does not increase the average distance by more than a factor of \(\frac{h}{h-1}\), \(h \geq 2\). This proves the edge-case of Winkler’s Conjecture for \(4\)-connected weighted graphs.

Furthermore, for \(3\)-edge-connected weighted graphs, it has been verified that the four-thirds conjecture holds for every weighted wheel \(W_p\), \(p \geq 4\), and for weighted \(K_{3,n}\) and \(K_{2,n}\) graphs for \(n \geq 2\).

A \((\Delta, D’, s)\)-digraph is a digraph with maximum out-degree \(\Delta\) such that after the deletion of any \(s\) of its vertices the resulting digraph has diameter at most \(D’\). Our concern is to find large, i.e. with order as large as possible, \((\Delta, D’, s)\)-digraphs. To this end, new families of digraphs satisfying a Menger-type condition are given. Namely, between any pair of non-adjacent vertices they have \(s + 1\) internally disjoint paths of length at most \(D’\). Then, new families of asymptotically optimal \((\Delta, D’, s)\)-digraphs are obtained.

Burr has shown that if \(G\) is any graph without isolates and \(H_0\) is any connected graph, every graph \(H\) obtained from \(H_0\) by subdividing a chosen edge sufficiently many times to create a long suspended path satisfies \(r(G, H) = (x(G) – 1)(|V(H)| – 1) + s(G)\), where \(s(G)\) is the largest number such that in every proper coloring of \(V(G)\) using \(\chi(G)\) colors, every color class has at least \(s(G)\) elements. In this paper, we prove a companion result for graphs obtained from \(H_0\) by adding sufficiently many pendant edges.

The Ramsey multiplicity \(R(G)\) of a graph \(G\) is defined as the smallest number of monochromatic copies of \(G\) in any two-coloring of the edges of \(K_r(q)\), where \(r(G)\) is the Ramsey number of \(G\). Here, we prove that \(R(K_4) \geq 4\).