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 _{i,j}{a}_{ij}f(r_i)f(c_j)\ge \sum _{i,j}{a}_{ij}\sum _{i}f(r_i)\sum _{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(\mathrm{mod}12)$. For any $n\ge 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\ge 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(\mathrm{\Omega })$ of the Dirichlet problem for a bounded domain $\mathrm{\Omega }$ in the Euclidean space ${\mathbf{R}}^n$ satisfies, ${\lambda }_1(\mathrm{\Omega })\ge {\lambda }_1(\mathbf{B})$ if $\text{vol}(\mathrm{\Omega })=\text{vol}(\mathbf{B})$, and equality holds only when $\mathrm{\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)\ge {\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\ge 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)\le 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)\le c(k)|G{|}^{1/k}/\log |G|$.
3. If girth $(G)\ge 5$ then $\chi (G)\le f(G)$ if $|G|\ge 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, $\mathrm{\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, $\mathrm{\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})$.

In this paper, we prove that the Equitable $\mathrm{\Delta }$-Coloring Conjecture holds for planar graphs with maximum degree $\mathrm{\Delta }\ge 13$.

An array $A[i,j]$, $1\le i\le n,1\le j\le n$, has a period $A[p,p]$ of dimension $p\times p$ if $A[i,j]=A[i+p,j+p]$ for $i,j=1\dots n-p$. The period of $A_{p,p}$ is the shortest such $p$.

We study two-dimensional pattern matching, and several other related problems, all of which depend on finding the period of an array.

In summary, finding the period of an array in parallel using $p$ processors for general alphabets has the following bounds:

$$\{\begin{array}{ll}\mathrm{\Theta }\left(\frac{n^2}{p}\right)& \text{if }p\le \frac{n^2}{\log \log n},n>{17}^3(1.1)\\ \mathrm{\Theta }(\log \log n)& \text{if }\frac{n^2}{\log \log n}<p{17}^3(1.2)\\ \mathrm{\Theta }(\log {\log }_{\frac{2p}{n^2}}p)& \text{if }{n}^2\le p{17}^3(1.3)\\ \mathrm{\Theta }(\log {\log }_{\frac{2p}{n^2}}p)& \text{if }{n}^2{\log }^{2}n\le p\le n^4,n\text{ large enough}(1.4)\end{array}$$

In [5] Kløve gave tables of the best bounds known on the size of optimal difference triangle sets. In this note, we give examples of difference triangle sets found by computer search which improve on the upper bounds in [5]. In four cases, these examples are proved to be optimal.

A Latin square $(S,\cdot )$ is said to be $(3,1,2)$-\emph{conjugate-orthogonal} if $x\cdot y=z\cdot w$, $x{\cdot }_{312}y=z{\cdot }_{312}w$ imply $x=z$ and $y=w$, for all $x,y,z,w\in S$, where $x_3{\cdot }_{312}{x}_1=x_2$ if and only if $x_1\cdot x_2=x_3$.

Such a Latin square is said to be \emph{holy} $((3,1,2)$-HCOLS for short) if it has disjoint and spanning holes corresponding to missing sub-Latin squares.

Let $(3,1,2)$-HCOLS$(h^n)$ denote a $(3,1,2)$-HCOLS of order $hn$ with $n$ holes of equal size $h$.

We show that, for any $h\ge 1$, a $(3,1,2)$-HCOLS$(h^n)$ exists if and only if $n\ge 4$, except $(n,h)=(6,1)$, and except possibly $(n,h)=(10,1)$ and $(4,2t+1)$ for $t\ge 1$.

Let $(3,1,2)$-ICOILS$(v,k)$ denote an idempotent $(3,1,2)$-COLS of order $v$ with a hole of size $k$.

We prove that a $(3,1,2)$-ICOILS$(v,k)$ exists for all $v\ge 3k+1$ and $1\le k\le 5$, except possibly $k=4$ and $v\in \{35,38\}$.

The main object of this paper is the construction of BIBD’s with $6\le k\le 11$ and $\lambda =1$. These balanced incomplete block designs can be simply constructed from some associated group divisible designs with the number of groups being a prime power, and it is these group divisible designs that are constructed directly. Other related designs are discussed.

We have carried out a large number of computer searches for the base sequences $BS(n+1,n)$ as well as for three important subsets known as Turyn sequences, normal sequences, and near-normal sequences. In the Appendix, we give an extensive list of $BS(n+1,n)$ for $n\le 32$. The existence question for Turyn sequences in $BS(n+1,n)$ was resolved previously for all $n\le 41$, and we extend this bound to $n\le 51$. We also show that the sets $BS(n+1,n)$ do not contain any normal sequences if $n=27$ or $n=28$. To each set $BS(n+1,n)$, we associate a finite graph ${\mathrm{\Gamma }}_n$, and determine these graphs completely for $n\le 27$. We show that $BS(m,n)=\mathrm{\varnothing }\text{if}m\ge 2n,n>1,\text{and}m+n\text{is odd}$,
and we also investigate the borderline case $m=2n–1$.