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.

Johannes H. Hattingh1, Michael A. Henning2
1Department of Mathematics Rand Afrikaans University P. O. Box 524, 2006 Aucklandpark, South Africa
2Department of Mathematics and Applied Mathematics University of Natal P. O. Box 375, 3200 Pietermaritzburg, South Africa
Abstract:

Let k1 be an integer and let G be a graph. A set D of vertices of G is a k-dominating set if every vertex of V(G)D is within distance k of some vertex of D. The graph G is called well-k-dominated if every minimal k-dominating set of G is of the same cardinality. A characterization of block graphs that are well-k-dominated is presented, where a block graph is a graph in which each of its blocks is complete.

Ralph J. Faudree1, Brendan D. McKay2
1Department of Mathematical Sciences Memphi State University Memphis, Tennessee, USA
2Computer Science Department Australian National University Canberra, ACT, Australia
Abstract:

It was conjectured by Paul Erdős that if G is a graph with chromatic number at least k, then the diagonal Ramsey number r(G)r(Kk). That is, the complete graph Kk has the smallest diagonal Ramsey number among the graphs of chromatic number k. This conjecture is shown to be false for k=4 by verifying that r(W6)=17, where W6 is the wheel with 6 vertices, since it is well known that r(K4)=18. Computational techniques are used to determine r(W6) as well as the Ramsey numbers for other pairs of small order wheels.

Louis D. Nel1, Heidi J. Strayer2
1School of Computer Science Carleton University Ottawa, Ontario K1S 5B6
2Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1
Abstract:

A simple model of an unreliable network is a probabilistic graph in which each edge has an independent probability of being operational. The two-terminal reliability is the probability that specified source and target nodes are connected by a path of operating edges.
Upper bounds on the two-terminal reliability can be obtained from an edge-packing of the graph by source-target cutsets. However, the particular cutsets chosen can greatly affect the bound.
In this paper, we examine three cutset selection strategies, one of which is based on a transshipment formulation of the $k$-cut problem.
These cutset selection strategies allow heuristics for obtaining good upper bounds analogous to the pathset selection heuristics used for lower bounds.
The computational results for some example graphs from the literature provide insight for obtaining good edge-packing bounds. In particular, the computational results indicate that, for the purposes of generating good reliability bounds, the effect of allowing crossing cuts cannot be ignored, and should be incorporated in a good edge-packing heuristic.
This gives rise to the problem of finding a least cost cutset whose contraction in the graph reduces the source-target distance by exactly one.

Ciping Chen1, Guizhen Liu2
1P.O. Box 71 Beijing Agricultural Engineering University Qinghua Donglu, Beijing 100083, P. R. China
2Department of Mathematics Shandong University Jinan, Shandong P.R. China, 250100
Abstract:

Chvátal conjectured that if G is a k-tough graph and k|V(G)| is even, then G has a k-factor. In [5 it was proved that Chvátal’s conjecture is true. Katerinis[2] presented a toughness condition for a graph to have an [a,b]-factor. In this paper, we prove a stronger result: every (a1+a/b)-tough graph satisfying all necessary conditions has an [a,b]-factor containing any given edge and another [a,b]-factor excluding it. We also discuss some special cases of the above result.

C.C. Lindner1
1 Department of Algebra, Combinatorics and Analysis Auburn University Aubum, Alabama 36849-5307 USA.
B.A. Anderson1
1Department of Mathematics Arizona State University Tempe, Arizona U.S.A. 85287-1804
Abstract:

R.A. Bailey has conjectured that all finite groups except elementary Abelian 2-groups with more than one factor have 2-sequencings (i.e., terraces). She verified this for all groups of order n, n9. Results proved since the appearance of Bailey’s paper make it possible to raise this bound to n87 with n=64 omitted. Relatively few groups of order not 2n, n{4,5} must be handled by machine computation.

Jean Dunbar1, Renu Laskar2
1Mathematics Department Converse College Spartanburg, S.C. 29302
2Department of Mathematics Clemson University Clemson, S.C. 29634
Abstract:

A set S of vertices of a graph G=(V,E) is a global dominating set if S dominates both G and its complement G¯. The concept of global domination was first introduced by Sampathkumar. In this paper, we extend this notion to irredundancy. A set S of vertices will be called universal irredundant if S is irredundant in both G and G¯. A set S will be called global irredundant if for every x in S, x is an irredundant vertex in S either in G or in G¯. We investigate the universal irredundance and global irredundance parameters of a graph. It is also shown that the determination of the upper universal irredundance number of graphs is NP-Complete.

Stanislaw P. Radziszowski1
1Deprtment of Computer Science Rochester Institute of Technology Rochester, New York 14623
Abstract:

We enumerate by computer algorithms all simple t(t+7,t+1,2) designs for 1t5, i.e., for all possible t. This enumeration is new for t3. The number of nonisomorphic designs is equal to 3,13,27,1 and 1 for t=1,2,3,4 and 5, respectively. We also present some properties of these designs, including orders of their full automorphism groups and resolvability.

L. Caccetta1, Purwanto 1
1 School of Mathematics and Statistics Curtin University of Technology GPO Box U 1987, Perth, WA 6001 AUSTRALIA
Abstract:

Let G be a finite simple graph. The vertex clique covering number vcc(G) of G is the smallest number of cliques (complete subgraphs) needed to cover the vertex set of G. In this paper, we study the function vcc(G) for the case when G is r-regular and (r2)-edge-connected. A sharp upper bound for vcc(G) is determined. Further, the set of possible values of vcc(G) when G is a 4-regular connected graph is determined.

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;