A directed graph operation called pushing a vertex is studied. When a vertex is pushed, the orientation of each of its incident edges is reversed. We consider the problems of pushing vertices so as to produce: strongly connected digraphs semi-connected digraphs acyclic digraphs NP-completeness results are shown for each problem. It is shown that it is possible to create a directed path between any two vertices in a digraph; additional positive results and characterizations are shown for: tournaments outerplanar digraphs Hamiltonian cycles.

A Freeman-Youden rectangle (FYR) is a Graeco-Latin row-column design consisting of a balanced superimposition of two Youden squares. There are well known infinite series of FYRs of size \(q \times (2q+1)\) and \((q+1) \times (2q+1)\) where \(2q+1\) is a prime power congruent to \(3\) (modulo \(4\)). However, Preece and Cameron [9] additionally gave a single FYR of size \(7 \times 15\). This isolated example is now shown to belong to one of a set of infinite series of FYRs of size \(q \times (2q+1)\) where \(q\), but not necessarily \(2q+1\), is a prime power congruent to \(3\) (modulo \(4\)), \(q > 3\); there are associated series of FYRs of size \((q+1) \times (2q+1)\). Both the old and the new methodologies provide FYRs of sizes \(q \times (2q+1)\) and \((q+1) \times (2q+1)\) where both \(q\) and \(2q+1\) are congruent to \(3\) (modulo \(4\)), \(q > 3\); we give special attention to the smallest such size, namely \(11 \times 23\).

Let \(n_4(k,d)\) and \(d_4(n, k)\) denote the smallest value of \(n\) and the largest value of \(d\), respectively, for which there exists an \([n, k, d]\) code over the Galois field \(GF(4)\). It is known (cf. Boukliev [1] and Table B.2 in Hamada [6]) that (1) \(n_4(5, 179) =240\) or \(249\), \(n_4(5,181) = 243\) or \(244, n_4(5, 182) = 244\) or \(245, n_4(5, 185) = 248\) or \(249\) and (2) \(d_4(240,5) = 178\) or \(179\) and \(d_4(244,5) = 181\) or \(182\). The purpose of this paper is to prove that (1) \(74(5,179) = 241, n_4(5,181) = 244, n_4(5,182) = 245, n_4(5, 185) = 249\) and (2) \(d_4(240, 5) = 178\) and \(d_4(244,5) = 181\).

Let \(T_n\) denote any rooted tree with \(n\) nodes and let \(p = p(T_n)\) and \(q = q(T_n)\) denote the number of nodes at even and odd distance, respectively, from the root. We investigate the limiting distribution, expected value, and variance of the numbers \(D(T_n) = |p – q|\) when the trees \(T_n\) belong to certain simply generated families of trees.

In this paper, magic labelings of graphs are considered. These are labelings of the edges with integers such that the sum of the labels of incident edges is the same for all vertices. We particularly study positive magic labelings, where all labels are positive and different. A decomposition in terms of basis-graphs is described for such labelings. Basis-graphs are studied independently. A characterization of an algorithmic nature is given, leading to an integer linear programming problem. Some relations with other graph theoretical subjects, like vertex cycle covers, are discussed.

There are only two kinds of non-isomorphic consecutive vertex labelings of octahedron, and each of them can be deduced from the other. There is an algorithm to construct consecutive edge labelings. It is shown that there exist many non-isomorphic complementary consecutive edge labelings of octahedron.

It is known that there exists a one-to-one correspondence between the classes of equivalent \([n, n-k, 4]\)-codes over \(\mathrm{GF}(q)\) and the classes of projectively equivalent complete \(n\)-caps in \(\mathrm{PG}(k-1, q)\) (see [{20}], [{40}]). Hence all results on caps can be translated in terms of such codes. This fact stimulated many researches on the fundamental problem of determining the spectrum of the values of \(k\) for which there exist complete \(k\)-caps in \(\mathrm{PG}(n, q)\). This paper reports the result of a computer search for the spectrum of \(k\)’s that occur as a size of a complete \(k\)-cap in some finite projective spaces. The full catalog of such sizes \(k\) is given in the following projective spaces: \(\mathrm{PG}(3, q)\), for \(q \leq 5\), \(\mathrm{PG}(4, 2)\), \(\mathrm{PG}(4, 3)\), \(\mathrm{PG}(5, 2)\). Concrete examples of such caps are presented for each possible \(k\).\(^*\)

It is known (cf. {Hamada} [12] and {BrouwerEupen} and van Eupen [2] ) that (1) there is no ternary \([230, 6, 153]\) code meeting the Griesmer bound but (2) there exists a ternary \([232, 6, 153]\) code. This implies that \(n_3(6, 153) = 231\) or \(232\), where \(n_3(k, d)\) denotes the smallest value of \(n\) for which there exists a ternary \([n, k, d]\) code. The purpose of this paper is to prove that \(n_3(6, 153) = 232\) by proving the nonexistence of ternary \([231, 6, 153]\) codes.

If \(D\) is an acyclic digraph, its competition graph is an undirected graph with the same vertex set and an edge between vertices \(x\) and \(y\) if there is a vertex \(a\) so that \((x,a)\) and \((y,a)\) are both arcs of \(D\). If \(G\) is any graph, \(G\) together with sufficiently many isolated vertices is a competition graph, and the competition number of \(G\) is the smallest number of such isolated vertices. Roberts \([1978]\) gives an elimination procedure for estimating the competition number and Opsut \([1982]\) showed that this procedure could overestimate. In this paper, we modify that elimination procedure and then show that for a large class of graphs it calculates the competition number exactly.

A new concept of genus for finite groups, called stiff genus, is developed. Cases of stiff embeddings in orientable or nonorientable surfaces are dealt with. Computations of stiff genus of several classes of abelian and non-abelian groups are presented. A comparative analysis between the stiff genus and the Tucker symmetric genus is also undertaken.