It was proved by Ellingham \((1984)\) that every permutation graph either contains a subdivision of the Petersen graph or is edge-\(3\)-colorable. This theorem is an important partial result of Tutte’s Edge-\(3\)-Coloring Conjecture and is also very useful in the study of the Cycle Double Cover Conjecture. The main result in this paper is that every permutation graph contains either a subdivision of the Petersen graph or two \(4\)-circuits and therefore provides an alternative proof of the theorem of Ellingham. A corollary of the main result in this paper is that every uniquely edge-\(3\)-colorable permutation graph of order at least eight must contain a subdivision of the Petersen graph.

In this paper, the \(k\)-exponent and the \(k\)th upper multiexponent of primitive nearly reducible matrices are obtained and a bound on the \(k\)th lower multiexponent of this kind of matrices is given.

We call a simple \(t-(v,k)\) trade with maximum volume a maximal trade. In this paper, except for \(v = 6m+5\), \(m \geq 3\), maximal \(2-(v, 3)\) trades for all \(v\)’s are determined. In the latter case a bound for the volume of these trades is given.

Balanced ternary and generalized balanced ternary designs are constructed from any \((v, b, r, k)\) designs. These results generalise the earlier results of Diane Donovan ( 1985 ).

A graph is called \(K_{1,r}\)-free if it does not contain \(K_{1,r}\) as an induced subgraph. In this paper we generalize a theorem of Markus for Hamiltonicity of \(2\)-connected \(K_{1,r}\)-free (\(r \geq 5\)) graphs and present a sufficient condition for \(1\)-tough \(K_{1,r}\)-free (\(r \geq 4\)) graphs to be Hamiltonian.

Minimum degree two implies the existence of a cycle. Minimum degree \(3\) implies the existence of a cycle with a chord. We investigate minimum degree conditions to force the existence of a cycle with \(k\) chords.

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.