S. Lavanya1, S. Parameshwara Bhatta2
1Department of Mathematics Mangalore University Mangalagangothri Konaje, D.K. – 574199 India
2 Department of Mathematics Mangalore University Mangalagangothri Konaje, D.K. – 574199 India
Pavol Gvozdjak 1
1 Department of Mathematics and Statistics Simon Fraser University Burnaby, BC Canada V5A 186
Abstract:

The present paper studies bisectable trees, i.e., trees whose edges can be colored by two colors so that the induced monochromatic subgraphs are isomorphic. It is proved that the number of edges that have to be removed from a tree with maximum degree three to make it bisectable can be bounded by an absolute constant.

lliya Bluskov 1
1Department of Mathematics and Statistics University of Victoria, P.O.Box 3045 Victoria, British Columbia V8W 3P4 CANADA
Abstract:

We study the maximal intersection number of known Steiner systems and designs obtained from codes. By using a theorem of Driessen, together with some new observations, we obtain many new designs.

Benfu Yang 1, Wandi Wei 2
1Dept. of Mathematics Chengdu Teachers College Penzhou Sichuan Province P.R. China 611930
2Dept. of Mathematics Sichuan University Chengdu P.R. China 610064
Abstract:

Taking as blocks some subspace pairs in a finite unitary geometry, we construct a number of new Balanced Incomplete Block (BIB) designs and Partially Balanced Incomplete Block (PBIB) designs, and also give their parameters.

S. Ajoodani-Namini1,2
1 Center for Theoretical Physics and Mathematics (AEOI) P.O. Box 11365-8486, Tehran, Iran
2Department of Mathematics 253-37 California Institute of Technology Pasadena, CA 91125, USA
Abstract:

The support size of a factorization is the sum over the factors of the number of distinct edges in each factor. The spectrum of support sizes of \(l\lambda\)-factorizations of \(\lambda K_n\) and \(\lambda K_{n,n}\) are completely determined for all \(\lambda\) and \(n\).

Diane Donovan 1, Adelle Howse1, Peter Adams1
1Center for Combinatorics Mathematics Department The University of Queensland Queensland, 4072, Australia
Abstract:

Latin interchanges have been used to establish the existence of critical sets in Latin squares, to search for subsquare-free Latin squares, and to investigate the intersection sizes of Latin squares. Donald Keedwell was the first to study Latin interchanges in their
own right. This paper builds on Keedwell’s work and proves new results about the existence of Latin interchanges.

Darryn E. Bryant1, A. Khodkar 1
1 Centre for Combinatorics Department of Mathematics The University of Queensland Queensland 4072 Australia
Abstract:

A balanced ternary design of order nine with block size three, index two, and \(\rho_2 = 1\) is a collection of multi-subsets of size \(3\) (of type \(\{x, y, z\}\) or \(\{x, x, y\}\)) called blocks, chosen from a \(9\)-set, in which each unordered pair of distinct elements occurs twice, possibly in one block, and in which each element is repeated in just one block. So there are precisely \(9\) blocks of type \(\{x, x, y\}\). We denote such a design by \((9; 1; 3, 2)\) BTD. In this note, we describe the procedures we have used to
determine that there are exactly \(1475\) non-isomorphic \((9; 1; 3, 2)\) BTDs.

R.E.L. Aldred 1, Brendan D. McKay 2, N.C. Wormald 3
1 Department of Mathematics and Statistics University of Otago P.O. Box 56 Dunedin, New Zealand
2Department of Computer Science Australian National University Canberra, A.C.T. 0200, Australia
3Department of Mathematics University of Melbourne Parkville, Victoria 3052, Australia
Abstract:

A graph \(G\) is said to be \emph{hypohamiltonian} if \(G\) is not Hamiltonian but for each \(v \in V(G)\), the vertex-deleted subgraph \(G – v\) is Hamiltonian. In this paper, we show that there is no hypohamiltonian graph on \(17\) vertices and thereby complete the answer to the question, “For which values of \(n\) do there exist hypohamiltonian graphs
on \(n\) vertices?”. In addition, we present an exhaustive list of hypohamiltonian graphs on fewer than \(18\) vertices and extend previously obtained results for cubic hypohamiltonian graphs.

Yeow Meng Chee 1, Charles J. Colbourn2, Robert P. Gallant2, Alan C. H. Ling2
1Department of Computer Science University of Waterloo Waterloo, Ontario Canada N2L 3G1
2Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario Canada N2L 3G1
Abstract:

We consider the problem of constructing pairwise balanced designs of order \(v\) with a hole of size \(k\). This problem was addressed by Hartman and Heinrich who gave an almost complete solution. To date, there remain fifteen unresolved cases. In this paper, we construct designs settling all of these.

David A. Pike1
1Department of Discrete and Statistical Sciences Auburn University, Auburn, Alabama, USA. 36849-5307
Abstract:

All non-Hamiltonian cubic \(2\)-edge-connected graphs, including all snarks, on \(16\) or fewer vertices are listed, along with some of their properties. Questions concerning the existence of graphs with certain properties are posed.

B. Baéa 1, I. Hollander 1, Ko-Wei Lih2
1 Department of Mathematics Technical University Koéice, Slovak Republic
2 Institute of Mathematics Academia Sinica Taipei, Taiwan, Republic of China
Abstract:

We deal with finite graphs which admit a labeling of edges by pairwise different positive integers from the set \(\{1, 2, \ldots, |E(G)|\}\) in such a way that the sum of the labels of the edges incident to a particular vertex is the same for all vertices. We construct edge labelings for two families of quartic graphs, i.e., regular graphs of degree \(d = 4\).

A. Vera Lépez1, M.A. Garefa Sanchez1
1 Universidad del Pais Vasco Facultad de Ciencias Departamento de Matematicas Apartado Correos 644 48080 Bilbao, Spain
Abstract:

Kibler, Baumert, Lander, and Kopilovich (cf. [7], [1], [10], and [8] respectively), studied the existence of \( (v, k, \lambda) \)-abelian difference sets with \( k \leq 100 \). In Lander and Kopilovich’s works, there were \( 13 \) and \( 8 \) \( (v, k, \lambda) \) tuples, respectively, in which the problem was open. Later, several authors have completed these studies and nowadays the problem is open for \( 6 \) and \( 7 \) tuples,
respectively. Jungnickel (cf. [9]) lists some unsolved problems on difference sets. One of them is to extend Lander’s table somewhat. By following this idea, this paper deals with the existence or non-existence of \( (v, k, \lambda) \)-abelian difference sets with \( 100 < k \leq 150 \). There exist \( 277 \) tuples that satisfy the basic relationship between the parameters \( v \), \( k \), and \( \lambda \), \( k \leq v/2 \), Schutzenberger and Bruck-Chowla-Ryser's necessary conditions, and \( 100 < k \leq 150 \). In order to reduce this number, we have written in C several programs which implement some known criteria on non-existence of difference sets. We conclude that the only \( (v, k, \lambda) \) tuples, with \( 100 < k \leq 150 \), for which a difference set in some abelian group of order \( v \) can exist are \begin{align*} &(10303, 102, 1), (10713, 104, 1), (211, 105, 52), (11557, 108, 1), \\ &(223, 111, 55), (11991, 110, 1), (227, 113, 56), (12883, 114, 1), \\ &(378, 117, 386), (239, 119, 59), (256, 120, 56), (364, 121, 40), \\ &(243, 121, 60), (14763, 122, 1), (251, 125, 62), (15751, 126, 1), \\ &(351, 126, 45), (255, 127, 63), (16257, 128, 1), (16513, 129, 1), \\ &(263, 131, 65), (17293, 132, 1), (1573, 132, 11), (1464, 133, 12), \\ &(271, 135, 67), (18907, 138, 1), (19461, 140, 1), (283, 141, 70), \\ &(22351, 150, 1), (261, 105, 42), (429, 198, 27), (1200, 110, 10), \\ &(768, 118, 18), (841, 120, 17), (715, 120, 20), (5085, 124, 3), \\ &(837, 133, 21), (419, 133, 42), (1225, 136, 15), (361, 136, 51), \\ &(1975, 141, 10), (1161, 145, 18), (465, 145, 45), (5440, 148, 4), \\ &(448, 150, 50). \end{align*} It is known that there exist difference sets for the first \( 29 \) tuples and the problem is open for the remaining \( 16 \). Besides, in Table 1, we give the criterion that we have applied to determine the non-existence of \( (v, k, \lambda) \)-difference sets for the rest of the tuples.

D. Kirby 1, H.P. Williams 1
1 Faculty of Mathematical Studies University of Southampton United Kingdom
Abstract:

It is shown how any integral monoid can be represented as the projection of the intersection of the solution set of a finite collection of linear inequalities, and a lattice, both in a possibly higher dimension. This in turn can be used to derive a known representation using Chvátal functions, in the same dimension as the monoid. Both representations can be regarded as discrete analogues of the classical theorems of Weyl and Minkowski, but applicable in non-polyhedral monoids.

Ronald D. Dutton1, Robert C. Brigham 2
1 Department of Computer Science
2Department of Mathematics University of Central Florida Orlando, Florida 32816
Abstract:

Both the bandwidth and additive bandwidth of a graph supply information about the storage requirements of a representation of the graph. In particular, the bandwidth measures how far \(1\)’s must be from the main diagonal of the graph’s adjacency matrix, while the additive bandwidth yields the same information with respect to the main contradiagonal. Thus, storage can be significantly reduced from that required by the full adjacency matrix if at least one of the two types of bandwidths is small, which is most likely to occur for sparse matrices. Alternatively, one could store a representation of the complement of the graph if one of its two bandwidths is small. We relate the additive bandwidth to other graphical invariants and then concentrate on Nordhaus-Gaddum type results to show that there are graphs for which both the bandwidth and the additive bandwidth of both the graph and its complement are large. In other words, some graphs require near maximum storage.

Qinglin Yu1,2
1 Department of Mathematics and Statistics University College of The Cariboo Kamloops, BC, Canada
2 Department of Mathematics and Statistics Simon Fraser University Burnaby, BC, Canada
Abstract:

A star-factor of a graph \(G\) is a spanning subgraph of \(G\) such that each component of which is a star. In this paper, we study the structure of the graphs with a unique star-factor and obtain an upper bound on the mnumber of edges such graphs can have. We also investigate the number of star-factors in a regular graph.

Chin-Mei Fu 1, Yuohg-Hwei Gwo1, Fang-Chuan Wu 1
1Department of Mathematics Tamkang University, Tamsui Taipei Shien, Taiwan 25137 Republic of China
Abstract:

Let \(J[v]\) denote the set of numbers \(k\) such that there exist two semi-symmetric Latin squares (SSLS) of order \(v\) which have \(k\) entries in common. In this paper, we show that \begin{align*}
J[3] &= \{0, 9\}, J[4] = \{0, 1, 3, 4, 9, 12, 16\}, \\
J[5] &= \{0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 18, 21, 25\}, \\
J[6] &= \{0, 1, 2, \ldots, 23, 24, 26, 27, 28, 29, 32, 36\}, \text{ and} \\
J[v] &= \{0, 1, 2, \ldots, v^2\} \setminus \{v^2-1, v^2-2, v^2-3, v^2-5, v^2-6\}
\end{align*}
for each \(v \geq 7\).

FE. Bennett 1, Ruizhong Wei 2, Hantao Zhang 3
1 Department of Mathematics Mount Saint Vincent University Halifax, Nova Scotia, B3M 2J6 Canada
2Department of Mathematics and Statistics University of Nebraska-Lincoln Lincoln, NE 68588 U.S.A.
3Computer Science Department The University of Iowa lowa City, IA 52242 U.S.A.
Abstract:

A holey perfect Mendelsohn design of type \(h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k}\) (HPMD\((h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k})\)), with block size four is equivalent to a frame idempotent quasigroup satisfying Stein’s third law with the same type, where a frame quasigroup of type \(h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k}\) means a quasigroup of order \(n\) with \(n_i\) missing subquasigroups (holes) of order \(h_i\), \(1 \leq i \leq k\),
which are disjoint and spanning, that is \(\sum_{1\leq i \leq k} n_ih_i = n\). In this paper, we investigate the existence of HPMD\((2^n3^1)\) and show that an HPMD\((2^n3^1)\) exists if and only if \(n \geq 4\). As an application, we readily obtain HSOLS\((2^n3^1)\) and establish the existence of \((2,3,1)\) [or \((3,1,2)\)]-HCOLS\((2^n3^1)\) for all \(n \geq 4\).

Terry A. McKee1
1Department of Mathematics and Statistics Wright State University Dayton, Ohio USA 45435
Abstract:

Much of chordal graph theory and its applications is based on chordal graphs being the intersection graphs of subtrees of trees. This suggests also looking at intersection graphs of subgraphs of chordal graphs, and so on, with appropriate conditions imposed on the subgraphs.
This paper investigates such a hierarchy of generalizations of “chordal-type” graphs, emphasizing the so-called “ekachordal graphs” — those next in line beyond chordal
graphs. Parts of the theory of chordal graphs do carry over to chordal-type graphs, including a recursive, elimination characterization for ekachordal graphs.

C.J. Colbourn 1, D.R. Stinson2, L. Zhu3
1 Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, Canada N2L 3Gi
2 Department of Computer Science and Engineering University of Nebraska Lincoln, NE 68588-0115, U.S.A.
3 Department of Mathematics Suzhou University Suzhou, 215006, China
Abstract:

We present a new construction to obtain frames with block size four using certain skew Room frames. The existence results of Rees and Stinson for frames with block size four are improved, especially nfor hole sizes divisible by \(6\). As a by-product of the skew Room
frames we construct, we are also able to show that a resolvable \((K_4 – e)\)-design with \(60t + 16\) points exists if \(t \geq 0\) and \(t \neq 8, 12\).

Frank Rhodes 1
1 Department of Mathematics University of Southampton. Southampton SO17 1BJ
Abstract:

It has been proved that the smallest rectangular board on which a \( (p, q) \)-knight’s graph is connected has sides \( p+q \) by \( 2q \) when \( p < q \). It has also been proved that these minimal connected knight's graphs are of genus \( 0 \) or \( 1 \), and that they are of genus \( 0 \) when \( p \) and \( q \) are of the form \( Md+1 \) and \( (M+1)d+1 \), with \( M \) a non-negative integer and \( d \) a positive odd integer. It is proved in this paper that the minimal connected knight's graph is of genus \( 1 \) in all other cases.

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;