Generalized Steiner triple systems, \(GS(2,3,n,g)\) are used to construct maximum constant weight codes over an alphabet of size \(g+1\) with distance \(3\) and weight \(3\) in which each codeword has length \(n\). The existence of \(GS(2,3,n,g)\) has been solved for \(g = 2,3,4,5,6,9\). The necessary conditions for the existence of a \(GS(2,3,n,g)\) are \((n-1)g \equiv 0 \pmod{2}\), \(n(n-1)g \equiv 0 \pmod{6}\), and \(n \geq g+2\). In this paper, the existence of a \(GS(2,3,7,g)\) for any given \(g \geq 7\) is investigated. It is proved that if there exists a \(GS(2,3,n,g)\) for all \(n\), \(g+2 \leq n \leq 9g+158\), satisfying the two congruences, then the necessary conditions are also sufficient. As an application it is proved that the necessary conditions for the existence of a \(GS(2,3,n,g)\) are also sufficient for \(g = 7,8\).

The Ramsey numbers \(r(C_5,G)\) are determined for all graphs \(G\) of order six.

For a graph \(G\), let \(Var(G)\) denote the variance of the degree sequence of \(G\), let \(sq(G)\) denote the sum of the squares of the degrees of \(G\), and let \(t(G)\) denote the number of triangles in \(G\) and in its complement. The parameters are related by:
\(Var(G) = \frac{sq(G)}{n} – d^2\)
where \(d\) is the average degree of \(G\), and
\(t(G) = \binom{n}{3} + \frac{sq(G)}{2} – {m(n-1)}\)
Let \(Var(n)\) denote the maximum possible value of \(Var(G)\) where \(G\) has \(n\) vertices, and let \(sq(n,m)\) and \(t(n,m)\) denote the maximum possible values of \(sq(G)\) and \(t(G)\), respectively, where \(G\) has \(n\) vertices and \(m\) edges. We present a polynomial time algorithm which generates all the graphs with \(n\) vertices and \(m\) edges having \(sq(G) = sq(n,m)\) and \(t(G) = t(n,m)\). This extends a result of Olpp which determined \(t(n,m)\). We also determine \(Var(n)\) precisely for every \(n\), and show that
\[ Var(n) = \frac{q(q-1)^2}{n}(1-\frac{q}{n}) =\frac{27}{256}n^2=O(n)\]
where \(q = [\frac{3n}{4}] \),(if \(n \equiv 2 \pmod 4\) the rounding is up ) thereby improving upon previous results.

This paper defines a new graph invariant by considering the set of connected induced subgraphs of a graph and defining a polynomial whose coefficients are determined by this partially ordered set of subgraphs. We compute the polynomial for a variety of graphs and also determine the effects on the polynomial of various graph operations.

For two vertices \(u\) and \(v\) of a connected graph \(G\), the set \(H(u, v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\). Given a set \(S\) of vertices of \(G\), the union of all sets \(H(u,v)\) for \(u,v \in S\) is denoted by \(H(S)\). A convex set \(S\) satisfies \(H(S) = S\). The convex hull \([S]\) is the smallest convex set containing \(S\). The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S] = V(G)\). When \(H(S) = V(G)\), we call \(S\) a geodetic set. The minimum cardinality of a geodetic set is the geodetic number \(g(G)\). It is shown that every two integers \(a\) and \(b\) with \(2 \leq a \leq b\) are realizable as the hull and geodetic numbers, respectively, of some graph. For every nontrivial connected graph \(G\), we find that \(h(G) = h(G \times K_2)\). A graph \(F\) is a minimum hull subgraph if there exists a graph \(G\) containing \(F\) as induced subgraph such that \(V(F)\) is a minimum hull set for \(G\). Minimum hull subgraphs are characterized.

For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a dominating set if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A dominating set \(S \subseteq V\) is a paired-dominating set if the induced subgraph \(\langle S\rangle\) has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph \(\langle S\rangle \). A paired-dominating set \(S\) is an induced-paired dominating set if the edges of the matching are the induced edges of \(\langle S\rangle\), that is, \(\langle S\rangle\) is a set of independent edges. The minimum cardinality of an induced-paired dominating set of \(G\) is the induced-paired domination number \(\gamma_{ip}(G)\). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on \(\gamma_{ip}(G)\). A characterization of those triples \((a, b, c)\) of positive integers \(a \leq b \leq c\) for which a graph has domination number \(a\), paired-domination number \(b\), and induced-paired domination \(c\) is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.

Let \(M\) be an \(m\)-subset of \(\mathrm{PG}(k, 2)\), the finite projective geometry of dimension \(k\) over \(\mathrm{GF}(2)\). We would like to know the maximum number of lines that can be contained in \(M\). In this paper, we will not only give the maximum number of lines contained in \(m\)-subsets of \(\mathrm{PG}(k,2)\), but also construct an \(m\)-subset of \(\mathrm{PG}(k,2)\) containing the maximum number of lines.

Maximal partial spreads of the sizes \(13, 14, 15, \ldots, 22\) and \(26\) are described. They were found by using a computer. The computer also made a complete search for maximal partial spreads of size less than or equal to \(12\). No such maximal partial spreads were found.

Suppose we are given a set of sticks of various integer lengths, and that we have a knife that can cut as many as \(w\) sticks at a time. We wish to cut all the sticks up into pieces of unit length. By what procedure should the sticks be cut so that the total number of steps required is minimum? In this paper we show that the following natural algorithm is optimal: at each stage, choose the \(w\) longest sticks (or all sticks of length \(> 1\) if there are fewer than \(w\) of them) and cut them all in half (or as nearly in half as possible).