A simple inequality involving the number of components in an arbitrary graph becomes an equality precisely when the graph is chordal. This leads to a mechanism by which any graph parameter, if always at least as large as the number of components, corresponds to a subfamily of chordal graphs. As an example, the domination number corresponds to the well-studied family of \(P_4, C_4\)-free graphs.

In this paper, we will be concerned with graphs \(G\) satisfying: \(G\) is isometrically embeddable in a hypercube; \(|C(a,b)| = |C(b,a)|\) for every edge \([a,b]\) of \(G\). where \(C(a,b)\) is the set of vertices nearer to \(a\) than to \(b\). Some properties of such graphs are shown; in particular, it is shown that all such graphs \(G\) are \(3\)-connected if \(G\) has at least two edges and \(G\) is not a cycle.

We improve upon Caro’s general polynomial characterizations, all in terms of modified line graphs, restricted to decomposing a graph into isomorphic subgraphs \(H\) with two edges. Firstly, we solve the problem for a multigraph; secondly, we decrease the polynomial bound on complexity if \(H = 2K_2\) and provide an original sufficient condition which can be verified in linear time if \(H = P_3\).

It has been shown by Sittampalam and Keedwell that weak critical sets exist for certain latin squares of order six and that previously claimed examples (for certain latin squares of order \(12\)) are incorrect. This led to the question raised in the title of this paper. Our purpose is to show that five is the smallest order for which weakly completable critical sets exist. In the process of proving this result, we show that, for each of the two types of latin square of order four, all minimal critical sets are of the same type.

We show that if \(G\) is a \((2k-1)\)-connected graph \((k \geq 2)\) with radius \(r\), then \(r \leq \left\lfloor \frac{|V(G)|+2k+9}{2k}\right\rfloor\).

A Cayley digraph \({Cay}(G, S)\) of a finite group \(G\) is isomorphic to another Cayley digraph \({Cay}(G, T)\) for each automorphism \(\sigma\) of \(G\). We will call \({Cay}(G, S)\) a CI-graph if, for each Cayley digraph \({Cay}(G,T)\), whenever \({Cay}(G, S) \cong {Cay}(G,T)\) there exists an automorphism \(\sigma\) of \(G\) such that \(S^\sigma = T\). Further, for a positive integer \(m\), if all Cayley digraphs of \(G\) of out-valency \(m\) are CI-graphs, then \(G\) is said to have the \(m\)-DCI property. This paper shows that for any positive integer \(m\), if a finite abelian group \(G\) has the \(m\)-DCI property, then all Sylow subgroups of \(G\) are homocyclic.

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.