
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 93-95
- Published: 31/10/1995
\(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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 65-92
- Published: 31/10/1995
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 55-63
- Published: 31/10/1995
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 48-54
- Published: 31/10/1995
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\).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 33-47
- Published: 31/10/1995
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 019
- Pages: 3-31
- Published: 31/10/1995
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 018
- Pages: 245-254
- Published: 30/06/1995
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]\).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 018
- Pages: 233-244
- Published: 30/06/1995
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\).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 018
- Pages: 225-232
- Published: 30/06/1995
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\).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 018
- Pages: 214-224
- Published: 30/06/1995
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.