Wayne Goddard1
1Dept of Computer Science University of Natal, Durban 4041, South Africa, and Dept of Computer Science Clemson University, Clemson SC 29634, USA
Abstract:

For integers \( n \) and \( k \), we define \( r(n,k) \) as the average number of guesses needed to solve the game of Mastermind for \( n \) positions and \( k \) colours; and define \( f(n,k) \) as the maximum number of guesses needed. In this paper, we add more small values of the two parameters, and provide exact values for the case of \( n = 2 \). Finally, we comment on the asymptotics.

J. W. McGee1, C. A. Rodger2
1Department of Applied Math Illinois Institute of Technology 10 West 32nd St. Chicago, IL 60616
2Discrete and Statistical Sciences 235 Allison Lab. Auburn University, AL 36849-5307
Abstract:

In this paper, we solve the existence problem for covering the \( 2 \)-paths of \( K_n \) with \( 4 \)-paths. This also settles the spectrum of \( 3 \)-path systems of the line graph of \( K_n \). The proof technique allows the embedding problem for \( (4, 2) \)-path coverings to be settled.

Abstract:

The general linear group \( G \) over \( \mathbb{Z}/2^n\mathbb{Z} \) acts transitively on the finite upper half plane over \( \mathbb{Z}/2^n\mathbb{Z} \), where \( \mathbb{Z} \) denotes the ring of rational integers. In this paper, it is shown that the pair of \( G \) and the stabilizer of a point on the plane is a Gelfand pair.

Lutz Volkmann1
1Lehrstuhl II fiir Mathematik, RWTH Aachen, 52056 Aachen, Germany
Abstract:

A \( c \)-partite tournament is an orientation of a complete \( c \)-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament \( D \) is contained in directed cycles of all lengths \( 3, 6, 9, \ldots, |V(D)| \).

In this paper, we show that this conjecture is completely false. Namely, for each integer \( t \) with \( 3 \leq t \leq |V(D)| \), we present an infinite family of regular 3-partite tournaments \( D \) such that there exists an arc in \( D \) which is not contained in a directed cycle of length \( t \).

Mukund V. Bapat1, N. B. Limaye2
1Department of Mathematics, S. S. H. Kelkar College, Devgad, Maharashtra, INDIA
2Department of Mathematics, Vidyanagari, University of Mumbai, Mumbai – 400098. INDIA
Abstract:

Let \( G \) be a graph with vertex set \( V \) and edge set \( E \). A vertex labelling \( f: V \rightarrow \{0, 1, 2\} \) induces an edge labelling \( \overline{f}: E \rightarrow \{0, 1, 2\} \) defined by \( \overline{f}(uv) = |f(u) – f(v)| \). Let \( v_f(0), v_f(1), v_f(2) \) denote the number of vertices \( v \) with \( f(v) = 0, f(v) = 1 \) and \( f(v) = 2 \) respectively. Let \( e_f(0), e_f(1), e_f(2) \) be similarly defined. A graph is said to be 3-equitable if there exists a vertex labelling \( f \) such that \( |v_f(i) – v_f(j)| \leq 1 \) and \( |e_f(i) – e_f(j)| \leq 1 \) for \( 0 \leq i, j \leq 2 \). In this paper, we show that every multiple shell \( MS\{n_1^{t_1}, \ldots, n_r^{t_r}\} \) is 3-equitable for all positive integers \( n_1, \ldots, n_r, t_1, \ldots, t_r \).

Linda Eroh1
1University of Wisconsin Oshkosh
Abstract:

The rainbow Ramsey number \( RR(G_1, G_2) \) or constrained Ramsey number \( f(G_1,G_2) \) of two graphs \( G_1 \) and \( G_2 \) is defined to be the minimum integer \( N \) such that any edge-coloring of the complete graph \( K_N \) with any number of colors must contain either a subgraph isomorphic to \( G_1 \) with every edge the same color or a subgraph isomorphic to \( G_2 \) with every edge a different color. This number exists if and only if \( G_1 \) is a star or \( G_2 \) is acyclic. In this paper, we present the conjecture that the constrained Ramsey number of \( nK_2 \) and \( mK_2 \) is \( m(n-1)+2 \), along with a proof in the case \( m \leq \frac{3}{2}(n-1) \).

Patric R. J. Ostergard1, Esa A. Seuranen1
1Department of Electrical and Communications Engineering Helsinki University of Technology P.O. Box 3000, 02015 HUT, Finland
Abstract:

A set \( C \subseteq \mathbb{F}_2^n \) is said to be an asymmetric covering code with radius \( R \) if every word \( x \in \mathbb{F}_2^n \) can be obtained by replacing \( 1 \) by \( 0 \) in at most \( R \) coordinates of a word in \( C \). In this paper, tabu search is employed in the search for good asymmetric covering codes of small length. Fifteen new upper bounds on the minimum size of such codes are obtained in the range \( n \leq 13 \).

Michael J. Letourneau1, Sheridan K. Houghtent1
1Department of Computer Science Brock University Ontario, Canada
Abstract:

We use exhaustive computer searches to show that there are exactly \( 36 \) codewords in an optimal ternary \( (11,7) \) code and exactly \( 13 \) codewords in an optimal ternary \( (14,10) \) code. We also enumerate inequivalent optimal ternary \( (14,10) \) codes and show that there are exactly \( 6151 \) such codes.

M. J. Grannell1, T. S. Griggs1, R. G, Stanton2
1Department of Pure Mathematics The Open University Walton Hall, Milton Keynes, MK7 6AA United Kingdom
2Department of Computer Science University of Manitoba Winnipeg, Manitoba, R3T 2N2 Canada
Abstract:

The minimum number of blocks having maximum size precisely four that are required to cover, exactly \( \lambda \) times, all pairs of elements from a set of cardinality \( v \) is denoted by \( g_\lambda^{(4)}(v) \). We present a complete solution to this problem for \( v = 3, 4, \) and \( 5 \).

Terry A. McKee1
1Department of Mathematics & Statistics Wright State University, Dayton, Ohio 45435 U.S.A.
Abstract:

Among the well-studied maximal planar graphs, those having the maximum possible number of 3-cycles are precisely the planar chordal graphs (meaning no induced cycles of lengths greater than three). This motivates a somewhat similar result connecting maximal planar bipartite graphs, 4-cycles, and planar chordal bipartite graphs (meaning bipartite with no induced cycles of lengths greater than four), together with characterizations of planar chordal bipartite graphs as radial graphs of outerplanar multigraphs.

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;