Let \(A = (a_{ij})\) be an \(m \times n\) nonnegative matrix, with row-sums \(r_i\) and column-sums \(c_j\). We show that \[
mn \sum\limits_{i,j} a_{ij} f(r_i) f(c_j) \geq \sum\limits_{i,j} a_{ij}\sum\limits_{i} f(r_i)\sum\limits_{j} f(c_j)
\] providing the function \(f\) meets certain conditions. When \(f\) is the identity function, this inequality is one proven by Atkinson, Watterson, and Moran in 1960. We also prove another inequality, of similar type, that refines a result of Ajtai, Komlós, and Szemerédi (1981).

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.