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.

Anthony E. Barkauskas1
1Mathematics Department University of Wisconsin — La Crosse La Crosse, Wisconsin 54601
Abstract:

An efficient dominating set \(S\) for a graph \(G\) is a set of vertices such that every vertex in \(G\) is in the closed neighborhood of exactly one vertex in \(S\). If \(G\) is connected and has no vertices of degree one, then \(G\) has a spanning tree which has an efficient dominating set. An \(O(n)\) algorithm for finding such a spanning tree and its efficient dominating set is given.

Bruce M. Landman1
1Department of Mathematics University of North Carolina at Greensboro Greensboro, North Carolina 27412
Abstract:

Numbers similar to the van der Waerden numbers \(w(n)\) are studied, where the class of arithmetic progressions is replaced by certain larger classes. If \(\mathcal{A}’\) is such a larger class, we define \(w'(n)\) to be the least positive integer such that every \(2\)-coloring of \(\{1, 2, \ldots, w'(n)\}\) will contain a monochromatic member of \(\mathcal{A}’\). We consider sequences of positive integers \(\{x_1, \ldots, x_n\}\) which satisfy \(x_i = a_i x_{i-1} + b_i x_{i-2}\) for \(i = 3, \ldots, n\) with various restrictions placed on the \(a_i\) and \(b_i\). Upper bounds are given for the corresponding functions \(w'(n)\). Further, it is shown that the existence of somewhat stronger bounds on \(w'(n)\) would imply certain bounds for \(w(n)\).

T. D. Porter1
1SOUTHERN ILLINOIS UNIVERSITY CARBONDALE, ILLINOIS 62901
Abstract:

For any graph \(G\), and all \(s = 2^k\), we show there is a partition of the vertex set of \(G\) into \(s\) sets \(U_1, \ldots, U_s\), so that both:
\(e(G[U_i]) \leq \frac{e(G)}{s^2} + \sqrt{\frac{e(G)}{s}}, \quad \text{for } i = 1, \ldots, s\) and \(\sum\limits_{i=1}^s e(G[U_i]) \leq \frac{e(G)}{s}.\)

Donald L. Kreher1
1Department of Mathematical Sciences Michigan Technological University Houghton, Michigan 49931-1295 U.S.A.
C. A. Barefoot1
1Department of Mathematics and Statistics New Mexico Institute of Mining and Technology Socorro, New Mexico 87801
Abstract:

The basic interpolation theorem states that if graph \(G\) contains spanning trees having \(m\) and \(n\) leaves, with \(m < n\), then for each integer \(k\) such that \(m < k < n\), \(G\) contains a spanning tree having \(k\) leaves. Various generalizations and related topics will be discussed.

Peter Adams1, Elizabeth J. Billington1, C. A. Rodger2
1Centre for Combinatorics Department of Mathematics The University of Queensland Queensland 4072 Australia
2Department of Discrete and Statistical Sciences 120 Mathematics Annex Auburn University Auburn, Alabama U.S.A. 36849-5307
Abstract:

We find the set of integers \(v\) for which \(\lambda K_v\) may be decomposed into sets of four triples forming Pasch configurations, for all \(\lambda\). We also remove the remaining exceptional values of \(v\) for decomposing \(K_v\) into sets of other four-triple configurations.

D. V. Chopra1
1Wichita State University Wichita, Kansas 67260-0033 U.S.A.
Abstract:

In this paper, we consider some combinatorial structures called balanced arrays (\(B\)-arrays) with a finite number of elements, and we derive some necessary conditions in the form of inequalities for the existence of these arrays. The results obtained here make use of the H\”{o}lder Inequality.

N. Chandrasekharan1, Sridhar Hannenhalli1
1Department of Computer Science University of Central Florida Orlando, FL 32816
Abstract:

We present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in \(O(n^{3})\) and \(O(n^2)\) time respectively. Our algorithm for computing the matching polynomial generalizes and improves the result in \([13]\) from \(O(n^3 \log n)\) time for trees and the chromatic polynomial algorithm improves the result in \([18]\) from \(O(n^4)\) time. The salient features of our results are the following:
Our techniques for computing the graph polynomials can be applied to certain other graph polynomials and other classes of graphs as well. Furthermore, our algorithms can also be parallelized into NC algorithms.

K. M. Koh1, K. Vijayan2
1Department of Mathematics National University of Singapore Singapore
2Department of Mathematics The University of Western Australia Western Australia
Abstract:

Given positive integers \(p\) and \(q\), a \((p, q)\)-colouring of a graph \(G\) is a mapping \(\theta: V(G) \rightarrow \{1, 2, \ldots, q\}\) such that \(\theta(u) \neq \theta(v)\) for all distinct vertices \(u, v\) in \(G\) whose distance \(d(u, v) \leq p\). The \(p\)th order chromatic number \(\chi^{(p)}(G)\) of \(G\) is the minimum value of \(q\) such that \(G\) admits a \((p, q)\)-colouring. \(G\) is said to be \((p, q)\)-maximally critical if \(\chi^{(p)}(G) = q\) and \(\chi^{(p)}(G + e) > q\) for each edge \(e\) not in \(G\).
In this paper, we study the structure of \((2, q)\)-maximally critical graphs. Some necessary or sufficient conditions for a graph to be \((2, q)\)-maximally critical are obtained. Let \(G\) be a \((2, q)\)-maximally critical graph with colour classes \(V_1, V_2, \ldots, V_q\). We show that if \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h \geq 1\) for some \(k\), where \(1 \leq k \leq q-1\), then \(h \leq h^*\), where

\[h^* = \max \left\{k, \min\{q – 1, 2(q – 1 – k)\}\right\}.\]

Furthermore, for each \(h\) with \(1 \leq h \leq h^*\), we are able to construct a \((2, q)\)-maximally critical connected graph with colour classes \(V_1, V_2, \ldots, V_q\) such that \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h\).

Erich Prisner1
1Mathematisches Seminar Universitat Hamburg Bundesstr. 55, 2000 Hamburg 13 FR. Germany
Abstract:

We define the class of \({hereditary \; clique-Helly \; graphs}\) or HCH \({graphs}\). It consists of those graphs, where the cliques of every induced subgraph obey the so-called `Helly-property’, namely, the total intersection of every family of pairwise intersecting cliques is nonempty. Several characterization and an \(O(|V|^2|E|)\) recognition algorithm for HCH graphs \(G = (V, E)\) are given. It is shown that the clique graph of every HCH graph is a HCH graph, and that conversely every HCH graph is the clique graph of some HCH graph. Finally, it is shown that HCH graphs \(G = (V, E)\) have at most \(|E|\) cliques, whence a maximum cardinality clique can be found in time \(O(|V||E|^2)\) in such a HCH 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;