D. de Caen 1
1Department of Mathematics and Statistics Queen’s University Kingston, Ontario K7L 3N6
Abstract:

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).

Elizabeth J. Billington1, C.C. Lindner2
1 Centre for Combinatorics Department of Mathematics The University of Queensland Queensland 4072 Australia
2 Department of Discrete and Statistical Sciences 120 Math Annex Auburn University Auburn, Alabama. 36849-5307 U.S.A.
Abstract:

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.

Atsushi Katsuda1, Hajime Urakawa 2
1Department of Mathematics Faculty of Science Okayama University Tsushima-naka 3-1-1 Okayama, 700 Japan
2Mathematics Laboratories Graduate School of Information Sciences Tohoku University Katahira 2-1-1 Sendai, 980-77 Japan
Abstract:

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\).

Yasuyuki Tsukui1
1 School of Business Administration Senshu University 2-1-1 Higashi-Mita Tamaku, Kawasaki 214-80 Japan
Abstract:

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.

Jitender S. Deogun1, Charles Riedesel1
1 Department of Computer Science and Engineering University of Nebraska — Lincoln Lincoln, NE 68588-0115, U.S.A.
Abstract:

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.

Marc Gysin1, Jennifer Seberry1
1 Centre for Computer Security Research Department of Computer Science The University of Wollongong Wollongong, NSW 2522 Australia
Abstract:

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\).

Konrad Piwakowski1, Stanistaw P. Radziszowski2
1 Department of Foundations of Informatics Technical University of Gdatisk 80-952 Gdatisk, Poland
2 Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA
Abstract:

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.

Yair Caro1
1School of Education Department of Mathematics University of Haifa-Oranim Tivon 36006 Isreal
Abstract:

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}\).
D.V. Chopra 1
1Department of Mathematics and Statistics Wichita State University Wichita, KS 67260-0033 (USA)
Abstract:

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.

Rommel Barbosa1, Bert Hartnelit2
1Department of Mathematics Universidade Federal do Mato Grosso Cuiabé, MT Brazil
2Department of Mathematics and Computing Science Saint Mary’s University Halifax, NS Canada
Abstract:

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.

Nirmala Achuthan 1, N.R. Achuthan 1, M. Simanihuruk 1
1 School of Mathematics and Statistics Curtin University of Technology GPO Box UI1987 Perth, Australia, 6001
Abstract:

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})\).

Yi Zhang1, Hian-Poh Yap1
1 Department of Mathematics National University of Singapore 10 Kent Ridge Crescent Singapore, 119260
Abstract:

In this paper, we prove that the Equitable \(\Delta\)-Coloring Conjecture holds for planar graphs with maximum degree \(\Delta \geq 13\).

Clive N. Galley1
1Department of Computer Science Kings College London University of London
Abstract:

An array \(A[i, j]\), \(1 \leq i \leq n, 1 \leq j \leq 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 \ldots 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{cases}
\Theta\left(\frac{n^2}{p}\right) & \text{if } p \leq \frac{n^2}{\log \log n}, n>17^3 \quad\quad\quad\quad\quad\quad\quad\quad(1.1) \\
\Theta(\log\log n) & \text{if } \frac{n^2}{\log \log n} < p 17^3 \quad\;\; \quad\quad\quad\quad (1.2) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \leq p 17^3 \quad \quad\quad\quad\quad (1.3) \\
\Theta\left(\log\log_{\frac{2p}{n^2}}{p}\right) & \text{if } n^2 \log^2 n \leq p \leq n^4, \text{ $n$ large enough} \quad (1.4)
\end{cases}
\]

James B. Shearer 1
1 Mathematical Sciences Department IBM Research Division T.J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598 U.S.A.
Abstract:

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.

Frank E. Bennett1, Hantao Zhangt 2
1 Department of Mathematics Mount Saint Vincent University Halifax, Nova Scotia B3M 236 Canada
2Computer Science Department The University of Iowa Iowa City, IA 52242 U.S.A.
Abstract:

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 \geq 1\), a \((3,1,2)\)-HCOLS\((h^n)\) exists if and only if \(n \geq 4\), except \((n,h) = (6,1)\), and except possibly \((n,h) = (10,1)\) and \((4,2t+1)\) for \(t \geq 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 \geq 3k+1\) and \(1 \leq k \leq 5\), except possibly \(k = 4\) and \(v \in \{35, 38\}\).

Malcolm Greig 1
1Greig Consulting 5685 Daffodil Drive West Vancouver B.C., Canada, V7W 1P2
Abstract:

The main object of this paper is the construction of BIBD’s with \(6 \leq k \leq 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.

Dragomir Z. Dokovié1
1 Department of Pure Mathematics University of Waterloo Waterloo, Ontario N2L 3G1
Abstract:

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 \leq 32\). The existence question for Turyn sequences in \(BS(n + 1, n)\) was resolved previously for all \(n \leq 41\), and we extend this bound to \(n \leq 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 \(\Gamma_{n}\), and determine these graphs completely for \(n \leq 27\). We show that \(BS(m,n) = \emptyset \quad \text{if} \quad m \geq 2n, \; n > 1, \; \text{and} \; m + n \; \text{is odd}\),
and we also investigate the borderline case \(m = 2n – 1\).

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;