Ida Pu1, Alan Gibbons2
1Department of Computin Goldsmiths College, University of London
2Department of Computer Science King’s College, London
Abstract:

Given the number of vertices \( n \), labelled graphs can easily be generated uniformly at random by simply selecting each edge independently with probability \( \frac{1}{2} \). With \( \frac{n(n-1)}{2} \) processors, this takes constant parallel time. In contrast, the problem of uniformly generating unlabelled graphs of size \( n \) is not so straightforward. In this paper, we describe an efficient parallelisation of a classic algorithm of Dixon and Wilf for the uniform generation of unlabelled graphs on \( n \) vertices. The algorithm runs in \( O(\log n) \) expected time on a CREW PRAM using \( n^2 \) processors.

L.R. Thimm1, D.L. Kreher1, P. Merkey1
1Department of Mathematical Sciences Michigan Technological University Houghton MI 49931-1295
Abstract:

We discuss a parallel programming method for solving the maximum clique problem. We use the partitioned shared memory programming language, Unified Parallel C, for the parallel implementation. The problem of load balancing is discussed and the steal stack is used to solve this problem. Implementation details are provided.

I. J. Dejter1, C. C. Lindner2, C. A. Rodger2, M. Meszka3
1Departament of Mathematics University of Puerto Rico Rio Piedras, PR 00931-3355 Puerto Rico
2Department of Mathematics Auburn University Auburn, Alabama 36849-5307 USA
3Faculty of Applied Mathematics AGH University of Science and Technology Krakéw Poland
Abstract:

A \( 4 \)-cycle system of order \( n \) is said to be almost resolvable provided its \( 4 \)-cycles can be partitioned into \( \frac{n-1}{2} \) almost parallel classes (i.e., \( \frac{n-1}{4} \) vertex-disjoint \( 4 \)-cycles) and a half parallel class (i.e., \( \frac{n-1}{8} \) vertex-disjoint \( 4 \)-cycles). We construct an almost resolvable \( 4 \)-cycle system of every order \( n \equiv 1 \pmod{8} \) except \( 9 \) (for which no such system exists) and possibly \( 33, 41, \) and \( 57 \).

Miao Liang1, Beiliang Du2
1Department of Foundation Suzhou Vocational University Suzhou 215104, P.R.China
2Department of Mathematics Suzhou University Suzhou 215006, P.R.China
Abstract:

Splitting balanced incomplete block designs were first formulated by Ogata, Kurosawa, Stinson, and Saido recently in the investigation of authentication codes. This article investigates the existence of splitting balanced incomplete block designs, i.e., \( (v, 2k, \lambda) \)-splitting BIBDs; we give the spectrum of \( (v, 2 \times 4, \lambda) \)-splitting BIBDs.

William Duckworth1, Alan Gibbons2
1Mathematical Sciences Institute, Australian National University, Canberra, ACT 0200, Australia
2Department of Computer Science, King’s College, London, WC2R 2L5S, UK.
Abstract:

In this paper, we first present new proofs, much shorter and much simpler than can be found elsewhere, of two facts about Hypercubes: that for the \( d \)-dimensional Hypercube, there exist sets of paths by which any \emph{permutation routing} task may be accomplished in at most \( 2d – 1 \) steps without queueing; and, when \( d \) is even, there exists an edge decomposition of the Hypercube into precisely \( \frac{d}{2} \) edge-disjoint Hamiltonian cycles. The permutation routing paths are computed off-line. Whether or not these paths may be computed by an online parallel algorithm in \( O(d) \)-time has long been an open question. We conclude by speculating on whether the use of a Hamiltonian decomposition of the Hypercube might lead to such an algorithm.

Miroslava Cimraékova1, Veerle Fack1
1Research Group Combinatorial Algorithms and Algorithmic Graph Theory! Department of Applied Mathematics and Computer Science, Ghent University, Krijgslaan 281~S9, B-9000 Ghent, Belgium,
Abstract:

The search for special substructures in combinatorial objects that have a lot of symmetry, such as searching for maximal partial ovoids or spreads in generalized quadrangles, can often be translated to a well-known algorithmic problem, such as a maximum clique problem in a graph. These problems are typically NP-hard. However, using standard backtracking strategies together with pruning techniques based on problem-specific properties, it is possible to obtain non-trivial results which are mathematically interesting. In some cases, heuristic techniques can also lead to interesting results. In this paper, we describe some techniques as well as new results obtained for maximal partial ovoids and spreads in generalized quadrangles.

Q.Q. Liu1, X.R. Ma1
1Department of Mathematics SuZhou University, SuZhou 215006, P.R.China
Abstract:

Built on earlier works of Larcombe on a certain class of non-terminating expansions of the sine function, we set up two new \( {_{}{3}F_2} \) summation formulas via integration.

Martin Grittmiiller1, Rolf Rees2, Nabil Shalaby2
1Department of Mathematics, University of Rostock Universitaetsplatz 1, 18051 Rostock, Germany
2Department of Mathematics and Statistics Memorial University of Newfoundland St. John’s, Newfoundland, Canada, A1C 587
Abstract:

In this paper, we investigate exhaustively the cyclically indecomposable triple systems \( TS_\lambda(v) \) for \( \lambda = 2, v \leq 33 \) and \( \lambda = 3, v \leq 21 \), and we identify the decomposable ones. We also construct, by using Skolem-type and Rosa-type sequences, cyclically indecomposable two-fold triple systems \( TS_2(v) \) for all admissible orders. Further, we investigate exhaustively all cyclic \( TS_2(v) \) that are constructed by Skolem-type and Rosa-type sequences up to \( v \leq 45 \) for indecomposability.

William F. Klostermeyer1, Gary MacGillivray2
1Dept. of Computer and Information Sciences University of North Florida Jacksonville, FL 32224-2669
2Dept. of Mathematics and Statistics University of Victoria Victoria, Canada
Abstract:

We show that if the independence number of a graph is \( \alpha \), then the eternal security number of the graph is at most \( \binom{\alpha+1}{2} \), solving a problem stated by Goddard, Hedetniemi, and Hedetniemi \([JCMCC, \text{ vol. } 52, \text{ pp. } 160-180]\).

Neville Robbins1
1Department of Mathematics San Francisco State University San Francisco, CA 94132 USA
Abstract:

Let \( n \) be a natural number. We obtain convolution-type formulas for the total number of parts in all partitions of \( n \) of several different kinds.

S. Georgiou1, I. Kotsireas2, C. Koukouvinos3
1Department of Statistics and Actuarial-Financial Mathematics, University of the Aegean, Karlovassi 83200, Samos, Greece.
2Department of Physics and Computer Science, Wilfrid Laurier University, 75 University Avenue West, Waterloo, Ontario N2L 3C5, Canada.
3Department of Mathematics National Technical University of Athens Zografou 15773, Athens, Greece
Abstract:

In this paper, we establish a doubling method to construct inequivalent Hadamard matrices of order \( 2n \), from Hadamard matrices of order \( n \). Our doubling method uses heavily the symmetric group \( S_n \), where \( n \) is the order of a Hadamard matrix. We improve the efficiency of the method by introducing some group-theoretical heuristics. Using the doubling method in conjunction with the standard 4-row profile criterion, we have constructed several millions of new inequivalent Hadamard matrices of orders 48, 56, 64, 72, 80, 88, 96, and several hundreds of inequivalent Hadamard matrices of orders 672 and 856. The Magma code segments, included in this paper, allow one to compute many more inequivalent Hadamard matrices of the above orders and all other orders of the form \( 8t \).

AP Burger1, JH van Vuuren1
1Department of Logistics, University of Stellenbosch, Private Bag X1, Matieland, 7602, South Africa
Abstract:

In this paper, we determine analytically the number of balanced, unlabelled, 3-member covers of an unlabelled finite set, which is then used to find the number of non-isomorphic optimal lottery sets of cardinality three. We also determine numerically the number of non-isomorphic optimal playing sets for lotteries in which a single correct number is required to win a prize.

Margaret-Ellen Messinger1
1Dalhousie University, Halifax, Nova Scotia, Canada
Abstract:

A fire breaks out on a graph \( G \) and then \( f \) firefighters protect \( f \) vertices. At each subsequent interval, the fire spreads to all adjacent unprotected vertices, and firefighters protect \( f \) unburned vertices. Let \( f_G \) be the minimum number of firefighters needed to contain a fire on graph \( G \). If the triangular grid goes unprotected to time \( t = k \) when \( f_G \) firefighters arrive and begin protecting vertices, the fire can be contained by time \( t = 18k + 3 \) with at most \( 172k^2 + 58k + 5 \) vertices burned.

R.G. Stanton1
1Department of Computer Science University of Manitoba Winnipeg, MB, Canada R3T 2N2
Abstract:

A construction is given for a Restricted Sarvate-Beam Triple System in the case \( v = 8 \). This is the extremal case, since a Restricted SB Triple System cannot exist for \( v > 8 \).

Diya Bluskov1
1Department of Mathematics University of Northern BC Prince George, B.C. V2N 429 Canada
Abstract:

A \( t \)-\((v, k, \lambda) \) covering is a set of blocks of size \( k \) such that every \( t \)-subset of a set of \( v \) points is contained in at least \( \lambda \) blocks. The cardinality of the set of blocks is the size of the covering. The covering number \( C_\lambda(v, k, t) \) is the minimum size of a \( t \)-\((v, k, \lambda) \) covering. In this article, we find upper bounds on the size of \( t \)-\((v, k, 2) \) coverings for \( t = 3, 4 \), \( k = 5, 6 \), and \( v \leq 18 \). Twelve of these bounds are the exact covering numbers.

Arthur H. Busch1, Michael S. Jacobson1
1Department of Mathematics University of Colorado at Denver Denver, CO 80217
Abstract:

We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs \( G_{m,n} \). The bound is within \( 5 \) of a known upper bound that has been conjectured to be the exact domination number of the complete grid graphs.

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;