Let \(T = (V, E)\) be a tree on \(|V| = n\) vertices. \(T\) is graceful if there exists a bijection \(f : V \to \{0,1,\dots, n-1\}\) such that \(\{|f(u) – f(v)| \mid uv \in E\} = \{1,2,\dots,n-1\}\). If, moreover, \(T\) contains a perfect matching \(M\) and \(f\) can be chosen in such a way that \(f(u) + f(v) = n-1\) for every edge \(uv \in M\) (implying that \(\{|f(u) – f(v)| \mid uv \in M\} = \{1,3,\dots,n-1\}\)), then \(T\) is called strongly graceful. We show that the well-known conjecture that all trees are graceful is equivalent to the conjecture that all trees containing a perfect matching are strongly graceful. We also give some applications of this result.

Let \(D\) be an acyclic digraph. The competition graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there is a vertex \(x\) in \(D\) such that \((u,x)\) and \((v,x)\) are arcs of \(D\). The competition-common enemy graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there are vertices \(w\) and \(x\) in \(D\) such that \((w,u), (w,v), (u,x)\), and \((v,x)\) are arcs of \(D\). The competition number (respectively, double competition number) of a graph \(G\), denoted by \(k(G)\) (respectively, \(dk(G)\)), is the smallest number \(k\) such that \(G\) together with \(k\) isolated vertices is a competition graph (respectively, competition-common enemy graph) of an acyclic digraph.

It is known that \(dk(G) \leq k(G) + 1\) for any graph \(G\). In this paper, we give a sufficient condition under which a graph \(G\) satisfies \(dk(G) \leq k(G)\) and show that any connected triangle-free graph \(G\) with \(k(G) \geq 2\) satisfies that condition. We also give an upper bound for the double competition number of a connected triangle-free graph. Finally, we find an infinite family of graphs each member \(G\) of which satisfies \(k(G) = 2\) and \(dk(G) > k(G)\).

A \(k \times v\) double Youden rectangle (DYR) is a type of balanced Graeco-Latin design where each Roman letter occurs exactly once in each of the \(k\) rows, where each Greek letter occurs exactly once in each of the \(v\) columns, and where each Roman letter is paired exactly once with each Greek letter. The other properties of a DYR are of balance, and indeed the structure of a DYR incorporates that of a symmetric balanced incomplete block design (SBIBD). Few general methods of construction of DYRs are known, and these cover only some of the sizes \(k \times v\) with \(k = p\) (odd) or \(p+1\), and \(v = 2p + 1\). Computer searches have however produced DYRs for those such sizes, \(p \leq 11\), for which the existence of a DYR was previously in doubt. The new DYRs have cyclic structures. A consolidated table of DYRs of sizes \(p \times (2p +1)\) and \((p +1) \times (2p +1)\) is provided for \(p \leq 11\); for each of several of the sizes, DYRs are given for different inherent SBIBDs.

Block-intersection graphs of Steiner triple systems are considered. We prove that the block-intersection graphs of non-isomorphic Steiner triple systems are themselves non-isomorphic. We also prove that each Steiner triple system of order at most \(15\) has a Hamilton decomposable block-intersection graph.

A directed graph \(G\) is primitive if there exists a positive integer \(k\) such that for every pair \(u, v\) of vertices of \(G\) there is a walk from \(u\) to \(v\) of length \(k\). The least such \(k\) is called the exponent of \(G\). The exponent set \(E_n\) is the set of all integers \(k\) such that there is a primitive graph \(G\) on \(n\) vertices whose exponent is \(k\).

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.