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.

Gary L. Mullen1, Jau-Shyong Shiue2
1Department of Mathematics The Pennsylvania State University University Park, PA 16802
2Department of Mathematical Sciences University of Nevada, Las Vegas Las Vegas, NV 89154
J. Mark Keil1, Timothy B. Brecht1
1Department of Computational Science University of Saskatchewan Saskatoon, Canada S7N OWO
Abstract:

An \(h\)-cluster in a graph is a set of \(h\) vertices which maximizes the number of edges in the graph induced by these vertices. We show that the connected \(h\)-cluster problem is NP-complete on planar graphs.

R. G. Stanton1
1Department of Computer Science University of Manitoba Winnipeg, Canada R3T 2N2
Yong-Song Ho1, Sin-Min Lee2, Eric Seah3
1Department of Mathematics National University of Singapore REPUBLIC OF SINGAPORE
2 Department of Mathematics and Computer Science San Jose State University San Jose, California 95192 U.S.A.
3Department of Actuarial and Management Sciences University of Manitoba Winnipeg, Manitoba RIT 2N2 CANADA
Abstract:

Lee conjectures that for any \(k > 1\), a \((n,nk)\)-multigraph decomposable into \(k\) Hamiltonian cycles is edge-graceful if \(n\) is odd. We investigate the edge-gracefulness of a special class of regular multigraphs and show that the conjecture is true for this class of multigraphs.

Wang Jinhua1, Zhu Lie1
1Department of Mathematics Suzhou University Suzhou 215006 CHINA Abstract.
Abstract:

A balanced incomplete block design \(B[k, \alpha; v]\) is said to be a nested design if one can add a point to each block in the design and so obtain a block design \(B[k + 1, \beta; v]\). Stinson (1985) and Colbourn and Colbourn (1983) proved that the necessary condition for the existence of a nested \(B[3, \alpha; v]\) is also sufficient. In this paper, we investigate the case \(k = 4\) and show that the necessary condition for the existence of a nested \(B[4, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{4}\) and \(v \geq 5\), is also sufficient. To do this, we need the concept of a doubly nested design. A \(B[k, \alpha; v]\) is said to be doubly nested if the above \(B[k + 1, \beta; v]\) is also a nested design. When \(k = 3\), such a design is called a doubly nested triple system. We prove that the necessary condition for the existence of a doubly nested triple system \(B[3, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{2}\) and \(v \geq 5\), is also sufficient with the four possible exceptions \(v = 39\) and \(\alpha = 3, 9, 15, 21\).

Sin-Min Lee1, Sie-Keng Tan2
1Department of Mathematics and Computer Science San Jose State University San Jose, CA 95192, US
2Department of Mathematics National University of Singapore Kent Ridge, Singapore 0511
Abstract:

We exhibit here an infinite family of planar bipartite graphs which admit a \(k\)-graceful labeling for all \(k \geq 1\).

E. J. Farrell1, Earl Glen Whitehead, Jr.2
1Department of Mathematics The University of the West Indies St. Augustine, Trinidad
2Department of Mathematics and Statistics University of Pittsburgh Pittsburgh, PA 15260, USA
Abstract:

It is shown that under certain conditions, the embeddings of chessboards in square boards, yield non-isomorphic associated graphs which have the same chro- matic polynomials. In some cases, sets of non-isomorphic graphs with this property are formed.

B. Du1
1Department of Mathematics Suzhou University Suzhou 215006 China (PRC)
Abstract:

A diagonal Latin square is a Latin square whose main diagonal and back diagonal are both transversals. In this paper we give some constructions of pairwise orthogonal diagonal Latin squares (PODLS). As an application of such constructions we improve the known result about three PODLS and show that there exist three PODLS of order \(n\) whenever \(n > 46\); orders \(2 \leq n \leq 6\) are impossible, the only orders for which the existence is undecided are: \(10, 14, 15, 18, 21, 22, 26, 30, 33, 34\) and \(46\).

Venkatesh Raman1
1Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1
Abstract:

Finding the probability that there is an operational path between two designated vertices in a probabilistic computer network is known to be NP-hard. Edge-packing is an efficient strategy to compute a lower bound on the probability. We prove that finding the set of paths that produces the best edge-packing lower bound is NP-hard.

Zhi-Hong Chen1
1 Department of Mathematics Wayne State University Detroit, MI U.S.A. 48202
Abstract:

Using a contraction method, we find some best-possible sufficient conditions for \(3\)-edge-comected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

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;