Journal of Combinatorial Mathematics and Combinatorial Computing

ISSN: 0835-3026 (print) 2817-576X (online)

The Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC) embarked on its publishing journey in April 1987. From 2024 onward, it publishes four volumes per year in March, June, September and December. JCMCC has gained recognition and visibility in the academic community and is indexed in renowned databases such as MathSciNet, Zentralblatt, Engineering Village and Scopus. The scope of the journal includes; Combinatorial Mathematics, Combinatorial Computing, Artificial Intelligence and applications of Artificial Intelligence in various files.

Hesham El-Rewini1, Hesham H. Ali1
1Department of Math and Computer Science University of Nebraska at Omaha Omaha, NE 68182-0243
Abstract:

We study the problem of scheduling parallel programs with conditional branching on parallel processors. The major problem in having conditional branching is the non-determinism since the direction of a branch may be unknown until the program is midway in execution. In this paper, we overcome the problem of non-determinism by proposing a probabilistic model that distinguishes between branch and precedence relations in parallel programs. We approach the problem of scheduling task graphs that contain branches by representing all possible execution instances of the program by a single deterministic task graph, called the representative task graph. The representative task graph can be scheduled using one of the scheduling techniques used for deterministic cases. We also show that a schedule for the representative task graph can be used to obtain schedules for all execution instances of the program.

G.M. Hamilton1, A.J. W. Hilton2
1Department of Engineering University of Reading Whiteknights Reading, U.K.
2Department of Mathematics University of Reading Whiteknighis Reading, U.K,
Abstract:

We give a list of all graphs of maximum degree three and order at most sixteen which are critical with respect to the total chromatic number.

Rebecca A.H. Gower1, Sheila Oates-Williams1, Diane Donovan 1, Elizabeth J. Billington1
1 Department of Mathematics The University of Queensland Queensland 4072 Australia
Abstract:

In this paper we give a partial answer to a query of Lindner conceming the quasigroups arising from \(2\)-perfect \(6\)-cycle systems.

W. Gutjahr1
1Institut ftir Statistik und Informatik Universitat Wien A1010 Wien, Universititsstrasse 5/9 AUSTRIA
Abstract:

Consider the paths \(\pi_t(i_1), \ldots, \pi_t(i_k)\) from the root to the leaves \(i_1, \ldots, i_k\) in a random binary tree \(t\) with \(n\) internal nodes, where all such trees are assumed equally likely and the leaves are enumerated from left to right. We investigate, for fixed \(i_1, \ldots, i_k\) and \(n\), the average size of \(\pi_t(i_1)\cup \ldots \cup \pi_t(i_k)\) resp. of \(\pi_t(i_1)\cap \ldots \cap \pi_t(i_k)\) (the latter corresponding to the average depth of the smallest subtree containing \(i_1, \ldots, i_k\)). By a rotation argument, both problems are reduced to the case \(k=1\), for which a solution is known. Furthermore, formulas for the probability distributions of the depth of leaf \(i\), the distance between leaf \(i\) and \(j\) and the length of \(\pi_t(i) \cap \pi_t(j)\) are derived.

R. G. Stanton1, D. M.F. Stone1, E.A. Ruet d’Auteuil1
1Department of Computer Science University of Manitoba Winnipeg, Canada, R3T 2N2
A. LW. Hilton1,2, Zhao Cheng3
1Department of Mathematics University of Reading Whiteknights, Reading RG6 2AX United Kingdom
2Department of Mathematics, West Virginia University, Morgantown, WV 26506, U.S.A.
3West Virginia University Morgantown, WV 26506, U.S.A.
Abstract:

Chetwynd and Hilton made the following \({edge-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) > \frac{1}{3}|V(G)|\), then \(G\) is Class \(2\) if and only if it contains an overfull subgraph \(H\) with \(\Delta(H) = \Delta(G)\). They also made the following \({total-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) \geq \frac{1}{2}(|V(G)|+ 1)\), then \(G\) is Type \(2\) if and only if \(G\) contains a non-conformable subgraph \(H\) with \(\Delta(H) = \Delta(G)\). Here we show that if the edge-colouring conjecture is true for graphs of even order satisfying \(\Delta(G) > \frac{1}{2}|V(G)|\), then the total-colouring conjecture is true for graphs of odd order satisfying \(\delta(G) \geq \frac{3}{4}{|V(G)|} – \frac{1}{4}\) and \(\text{def}(G) \geq 2(\Delta(G) – \delta(G) + 1)\).

Theresa P. Vaughan1
1Department of Mathematics University of North Carolina at Greensboro Greensboro, NC 27412
Edward Spence1
1Department of Mathematics University of Glasgow Glasgow G12 8QQ Scotland
Abstract:

We correct an omission by Mathon in his classification of symmetric \((31, 10, 3)\)-designs with a non-trivial automorphism group and find that there are a further six such designs, all with an automorphism group of order \(3\).

E. J. Cockayne1, G. MacGillivray2, C. M. Mynhardt3
1University of Victoria, B.C., Canada
2University of Regina, Sask., Canada
3University of South Africa, Pretoria, South Africa
Abstract:

A \({dominating \; function}\) is a feasible solution to the LP relaxation of the minimum dominating set \(0-1\) integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree \({T}\) can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in \({T}\), if one exists.

Igrgen Bang-Jensen1, Gary MacGillivray2
1Department of Computer Science University of Copenhagen DK-2100, Denmark
2Department of Mathematics and Statistics University of Regina Saskatchewan, Canada, $48 0A2
Abstract:

Let \(H\) be a digraph whose vertices are called colours. Informally, an \(H\)-colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that adjacent vertices receive adjacent colours. In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem “Does there exist an \(H\)-colouring of a given digraph \(G\)?”. In particular, we prove that the \(H\)-colouring problem is NP-complete if the digraph \(H\) consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as \(H\) does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete \(H\)-colouring problems.

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;