A bowtie is a simple graph on \(5\) vertices with \(6\) edges, which consists of a pair of edge-disjoint triangles having one common vertex. A bowtie design of order \(n\) is an edge-disjoint decomposition of the complete undirected graph \(K_n\) into bowties. These exist if and only if \(n \equiv 1\) or \(9 \pmod{12}\). For any \(n \geq 5\), a maximum packing of the complete undirected graph \(K_n\) with bowties is a collection of edge-disjoint bowties picked from \(K_n\), of maximum cardinality. The unused edges of \(K_n\) in this decomposition, if any, form the leave of the packing, which is necessarily a set with cardinality as small as possible. In this paper, a maximum packing of \(K_n\) with bowties is found, for all \(n \geq 5\) and for all possible leaves.

We give a graph theoretic analogue of the celebrated Faber-Krahn inequality, that is, the first eigenvalue \(\lambda_1(\Omega)\) of the Dirichlet problem for a bounded domain \(\Omega\) in the Euclidean space \(\mathbf{R}^n\) satisfies, \(\lambda_1(\Omega) \geq \lambda_1(\mathbf{B})\) if \(\text{vol}(\Omega) = \text{vol}(\mathbf{B})\), and equality holds only when \(\Omega\) is a ball \(\mathbf{B}\).The first eigenvalue \(\lambda_1(G)\) of the Dirichlet problem of a graph \(G = (V, E)\) with boundary satisfies, if the number of edges equals \(m\), \(\lambda_1(G) \geq \lambda_1(L_m)\), and equality holds only when \(G\) is the linear graph \(L_m\).

The edge-reduction of a simple regular graph is an operation which removes two vertices and preserves the regularity. It has played an important role in the study of cubic graphs [6,7,8]. Our main purpose is to study the structure of edge-irreducible quartic graphs. All edge-irreducible quartic graphs are determined from a constructive viewpoint. Then, a unique decomposition theorem for edge-irreducible quartic graphs is obtained.

In this paper, we employ the structures of a permutation graph as exhibited in the Euclidean representation to solve the existence and construction problems of Hamiltonian cycles on permutation graphs. We define and prove the existence of a layered Hamiltonian cycle in a Hamiltonian permutation graph. A linear (in size) time and (in order) space algorithm for construction of a layered Hamiltonian cycle on a permutation graph is presented and its
correctness proven.

Cyclotomy can be used to construct a variety of combinatorial designs, for example, supplementary difference sets, weighing matrices, and \(T\)-matrices. These designs may be obtained by using linear combinations of the incidence matrices of the cyclotomic cosets. However, cyclotomy only works in the prime and prime power cases. We present a generalisation of cyclotomy and introduce generalised cosets. Combinatorial designs can now be obtained by a search through all linear combinations of the incidence matrices of the generalised cosets. We believe that this search method is new. The generalisation works for all cases and is not restricted to prime powers. The paper presents some new combinatorial designs. We give a new construction for \(T\)-matrices of order \(87\) and hence an \({OD}(4 \times 87; 87, 87, 87, 87)\). We also give some \(D\)-optimal designs of order \(n = 2v = 2 \times 145, 2 \times 157, 2 \times 181\).

With the help of computer algorithms, we improve the upper bound on the classical three-color Ramsey number \(R(3,3,4)\), and thus we show that the exact value of this number is \(30\) or \(31\).We also present computer enumeration of all \(3\)-colorings of edges on at least \(14\) vertices without monochromatic triangles.

Conjecture 119 in the file “Written on the Wall”, which contains the output of the computer program “Graffiti” of Fajtlowicz, states: If \(G\) has girth \(5\) then its chromatic number is not more than the maximum frequency of occurrence of a degree in \(G\). Our main result provides an affirmative solution to this conjecture if \(|G| = n\) is sufficiently large. We prove:
Theorem. Let \(k \geq 2\) be a positive integer and let \(G\) be a \(C_{2k}\)-free graph (containing no cycle of length \(2k\)).

1. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)^{k-1} \sqrt{f(G)}/\log |G|\),
   where \(f(G)\) is the frequency of the mode of the degree sequence of \(G\).
2. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)|G|^{1/k}/\log |G|\).
3. If girth \((G) \geq 5\) then \(\chi(G) \leq f(G)\) if \(|G| \geq e^{49}\).

In this paper, we derive some inequalities on the existence of two-symbol balanced arrays (B-arrays) of strength five. We then apply these inequalities to obtain an upper bound on the number of constraints for these arrays, and provide an illustrative example.

A graph \(G\) is well-covered if every maximum independent set of vertices of \(G\) has the same cardinality. A graph \(G_1\) is an almost well-covered graph if it is not well-covered, but \(G_1 \setminus \{v\}\) is well-covered, \(\forall v \in V(G_1)\). Similarly, a graph \(H\) is a parity graph if every maximal independent set of vertices of \(H\) has the same parity, and a graph \(H_1\) is an almost parity graph if \(H_1\) is not a parity graph but \(H_1 \setminus \{h\}\) is a parity graph, \(\forall h \in V(H_1)\). Here, we will give a complete characterization of almost parity graphs. We also prove that claw-free parity graphs must be well-covered.

Let \(\mathcal{G}(p)\) denote the class of simple graphs of order \(p\). For a graph \(G\), the complement of \(G\) is denoted by \(\overline{G}\). For a positive integer \(n\), the \(n\)-path-chromatic number \(\chi_n(G)\) is the least number of colours that can be associated to the vertices of \(G\) such that not all the vertices on any path of length \(n\) receive the same colour. The Nordhaus-Gaddum Problem for the \(n\)-path-chromatic number of \(G\) is to find bounds for \(\chi_n(G) + \chi_n(\overline{G})\) and \(\chi_n(G) \cdot \chi_n(\overline{G})\) over the class \(\mathcal{G}(p)\). In this paper, we determine sharp lower bounds for the sum and the product of \(\chi_n(G)\) and \(\chi_n(\overline{G})\). Furthermore, we provide weak upper bounds for \(\chi_2(G) + \chi_2(\overline{G})\) and \(\chi_2(G) \cdot \chi_2(\overline{G})\).