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.

Norman J. Finizio1
1Department of Mathematics University of Rhode Island Kingston, Rhode Island 02881
Abstract:

\(Z\)-cyclic whist tournaments for \(q+1\) players, \({Wh}(q+1)\), where \(q\) is a prime, \(q \equiv 3 \pmod{4}\), are quite rare. Solutions for \(q = 3, 7, 11, 19, 23,\) and \(31\) were known in the early to mid 1890’s. Since that time no new such \({Wh}(q +1)\) have appeared.
Here we present \(Z\)-cyclic \({Wh}(q + 1)\) for \(q = 43, 47, 59\). Also presented for the first time is a \(Z\)-cyclic \({Wh}(45)\) and a \(Z\)-cyclic \({Wh}(40)\) that has the three person property. All of these results were obtained via the computer.

Ernest E. Shult1
1Department Of Mathematics Kansas State University Manhattan, KS 66506
Abstract:

There are many graphs with the property that every subgraph of a given simple isomorphism type can be completed to a larger subgraph which is embedded in its ambient parent graph in a nice way. Often, such graphs can be classified up to isomorphism. Here we survey theorems on polar space graphs, graphs with the cotriangle property, copolar graphs, Fischer spaces, and generalized Fischer spaces, as well as graphs with the odd coclique property.

Charles Riedesel1, Jitender S. Deogun1
1Department of Computer Science and Engineering University of Nebraska-Lincoln Lincoln, NE 68588-0115, U.S.A.
Abstract:

Permutation graphs, a well-known class of perfect graphs, has attracted the attention of numerous researchers. There are two noteworthy representations of permutation graphs. Permutation diagrams have been widely employed in theoretical and application research. The \(2\)-dimensional Euclidean representation suggested by Ore is relatively unknown and unexplored. In this paper, we demonstrate the utility of the latter representation in the investigation of the Hamiltonian Path problem in permutation graphs.

Cantian Lin1, Haiping Lin2
1Department of Mathematics University of Nevada, Las Vegas Las Vegas, NV 89154
2Department of Mathematics Southern Illinois University Carbondale, IL 62901
Abstract:

In this paper, we investigate the relationship between the profiles of Hadamard matrices and the weights of the doubly even self-orthogonal/dual \([n, m, d]\) codes from Hadamard matrices of order \(n = 8t\) with \(t \geq 1\). We show that such codes have \(m \leq \frac{n}{2}\), and give some computational results of doubly even self-orthogonal/dual \([n,m,d]\) codes from Hadamard matrices of order \(n = 8t\), with \(1 \leq t \leq 9\).

C.St.J.A. Nash-Williams1
1Department of Mathematics University of Reading Whiteknights, P.O. Box 220 Reading RG6 6AF, England
Abstract:

Let \(G\) be a finite strongly connected mixed graph (i.e., a graph with both undirected and directed edges, in which each vertex can be reached from every other vertex if directed edges can only be traversed in their direction of orientation). We establish a necessary and sufficient condition for it to be possible to transform some undirected edges of \(G\) into directed edges so that each vertex becomes the head of a prescribed number of newly directed edges and \(G\) remains strongly connected. A special case of this result yields a new proof (not requiring matroid techniques) of a necessary and sufficient condition for it to be possible to split each vertex of a finite connected graph into a prescribed number of vertices whilst preserving connectedness.

William Kocay1, Doug Stone1
1Computer Science Department University of Manitoba Winnipeg, Manitoba Canada R3T 2N2
Abstract:

The Balanced Network Search (BNS) is an algorithm which finds a maximum balanced flow in a balanced network \({N}\). This algorithm is a way of using network flows to solve a number of standard problems, including maximum matchings, the factor problem, maximum capacitated \(b\)-matchings, etc., in general graphs. The value of a maximum balanced flow equals the capacity of a minimum balanced edge-cut. Flow-carrying balanced networks contain structures called generalized blossoms. They are not based on odd cycles. Rather they are the connected components of a residual sub-network of \({N}\). An algorithm is given for finding a maximum balanced flow, by constructing complementary pairs of valid augmenting paths.

K. H. Chew1
1School of Mathematics University of New South Wales Sydney 2052 Australia
Abstract:

The total chromatic number \(\chi_T(G)\) of a graph \(G\) is the least number of colours needed to colour the edges and vertices of \(G\) so that no incident or adjacent elements receive the same colour. This paper shows that if \(G\) has maximum degree \(\Delta(G) > \frac{3}{4} |V(G)I – \frac{1}{2} \), then \(\chi_T(G) \leq \Delta(G) + 2\). A slightly weaker version of the result has earlier been proved by Hilton and Hind \([9]\). The proof here is shorter and simpler than the one given in \([9]\).

Michael A. Henning1, Ortrud R. Oellermann 2, Henda C. Swart2
1Department of Mathematics University of Natal Pietermaritzburg, South Africa
2Department of Mathematics University of Natal Durban, South Africa
Abstract:

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(\mathcal{D}\) of vertices of \(G\) is an \(n\)-dominating set (total \(n\)-dominating) set of \(G\) if every vertex of \(V(G) – \mathcal{D}\) (\(V(G)\), respectively) is within distance \(n\) from some vertex of \(\mathcal{D}\) other than itself. The minimum cardinality among all \(n\)-dominating sets (respectively, total \(n\)-dominating sets) of \(G\) is called the \(n\)-domination number (respectively, total \(n\)-domination number) and is denoted by \(\gamma_n(G)\) (respectively, \(\gamma_n^t(G)\)). A set \(\mathcal{I}\) of vertices of \(G\) is \(n\)-independent if the distance (in \(G\)) between every pair of distinct vertices of \(\mathcal{I}\) is at least \(n+1\). The minimum cardinality among all maximal \(n\)-independent sets of \(G\) is called the \(n\)-independence number of \(G\) and is denoted by \(i_n(G)\). Suppose \(\mathcal{I}_k\) is an \(n\)-independent set of \(k\) vertices of \(G\) for which there exists a vertex \(v\) of \(G\) that is within distance \(n\) from every vertex of \(\mathcal{I}_k\). Then a connected subgraph of minimum size that contains the vertices of \(\mathcal{I}_k \cup \{v\}\) is called an \(n\)-generalized \(K_{1,k}\) in \(G\). It is shown that if \(G\) contains no \(n\)-generalized \(K_{1,3}\), then \(\gamma_n(G) = i_n(G)\). Further, it is shown if \(G\) contains no \(n\)-generalized \(K_{1,{k+1}}\), \(k \geq 2\), then \(i_n(G) \leq (k-1)\gamma_n(G) – (k-2)\). It is shown that if \(G\) is a connected graph with at least \(n + 1\) vertices, then there exists a minimum \(n\)-dominating set \(\mathcal{D}\) of \(G\) such that for each \(d \in \mathcal{D}\), there exists a vertex \(v \in V(G) – \mathcal{D}\) at distance \(n\) from \(d\) and distance at least \(n+1\) from every vertex of \(\mathcal{D} – \{d\}\). Using this result, it is shown if \(G\) is a connected graph on \(p \geq 2n+1\) vertices, then \(\gamma_n(G) \leq p/(n + 1)\) and that \(i_n(G) + n\gamma_n(G) \leq p\). Finally, it is shown that if \(T\) is a tree on \(p \geq 2n + 1\) vertices, then \(i_n(G) + n\gamma_n^t(G) \leq p\).

Petr Lisonék1
1Research Institute for Symbolic Computation, Johannes Kepler University, Linz A~4040 Linz, Austria
Abstract:

Let \(a, b, c\) be fixed, pairwise relatively prime integers. We investigate the number of non-negative integral solutions of the equation \(ax + by + cz = n\) as a function of \(n\). We present a new algorithm that computes the “closed form” of this function. This algorithm is simple and its time performance is better than the performance of yet known algorithms. We also recall how to approximate the abovementioned function by a polynomial and we derive bounds on the “error” of this approximation for the case \(a = 1\).

Rachid Saad1
121, rue Ziane Said, la Scala El Biar, Alger Algeria
Abstract:

In this paper, scheduling problems with communication delays are considered. Formally, we are given a partial order relation \(\prec\) on a set of tasks \(T\), a set of processors \(P\), and a deadline \(d\). Supposing that a unit communication delay between two tasks \(a\) and \(b\) such that \(a \prec b\) occurs whenever \(a\) and \(b\) are scheduled on different processors, the question is: Can the tasks of \(T\) be scheduled on \(P\) within time \(d\)? It is shown here that the problem is NP-complete even if \(d = 4\). Also, for an unlimited number of processors, C. Picouleau has shown that for \(d = 8\) the problem is NP-complete. Here it is shown that it remains NP-complete for \(d \geq 6\) but is polynomially solvable for \(d < 6\), which closes the gap between P and NP for this problem, as regards the deadline.

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;