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.

Theresa P. Vaughan1, Frederick Portier2
1Bruce Landman University of North Carolina at Greensboro Greensboro, NC 27412
2Department of Mathematics and Computer Science Mount Saint Mary’s College Emmitsburg, MD 21727
Abstract:

We consider square arrays of numbers \(\{a(n, k)\}\), generalizing the binomial coefficients:
\(a(n, 0) = c_n\), where the \(c_n\) are non-negative real numbers; \(a(0, k) = c_0\), and if \(n, k > 0\), then \(a(n, k) = a(n, k – 1) + a(n – 1, k)\).
We give generating functions and arithmetical relations for these numbers. We show that every row of such an array is eventually log concave, and give a few sufficient conditions for columns to be eventually log concave. We also give a necessary condition for a column to be eventually log concave, and provide examples to show that there exist such arrays in which no column is eventually log concave.

D. V. Chopra1
1Wichita State University Wichita, Kansas U.S.A. 67208
Abstract:

In this paper, we obtain some necessary conditions for the existence of balanced arrays (\(B\)-arrays) of strength \(4\) and with two levels, and we state the usefulness of these conditions in obtaining an upper bound on the number of constraints for these B-arrays.

EJ. Farrell1, J. Grell1
1Department of Mathematics The University of West Indies St. Augustine, Trinidad
Abstract:

It is shown that the circuit polynomial of a graph, when weighted by the number of nodes in the circuits, does not characterize the graph, i.e., non-isomorphic graphs can have the same circuit polynomial. Some general theorems are given for constructing graphs with the same circuit polynomial (cocircuit graphs). Analogous results can be deduced for characteristic polynomials.

Zoltan Firedi 1,2, Nathan Linial3
1Mathematical Institute of the Hungarian Academy of Sciences, P,0, B. 127, Budapest 1364 Hungary
2Department of Mathematics University of Illinois Urbana, IL 61801, USA
3Hebrew University of Jerusalem
Abstract:

Given \(n\) real numbers whose sum is zero, find one of the numbers that is non-negative. In the model under consideration, an algorithm is allowed to compute \(p\) linear forms in each time step until it knows an answer. We prove that exactly \(\lceil{\log n}/{\log(p+1)} \rceil\) time steps are required. Some connections with parallel group-testing problems are pointed out.

Yang Yuansheng1, Peter Rowlinson2
1Department of Computer Science and Engineering Dalian University of Technology 116024 Dalian Liaoning Province People’s Republic of China
2Department of Mathematics University of Stirling Stirling FK9 4LA Scotland
Abstract:

With the help of a computer, the third Ramsey number is determined for each of the \(25\) graphs with five edges, five or more vertices, and no trivial components.

Zhang Ke Min1
1 Dept. of Mathematics, Nanjing University, Nanjing, 210008, Peoples Republic of China
Abstract:

In this paper, we prove that the size Ramsey number

\[\hat{r}(a_1K_{1,n_1}, a_2K_{1,n_2}, \ldots ,a_\ell K_{1,n_\ell}) = \left[\sum\limits_{i=1}^\ell {(a_i – 1)+1} \right] \left[\sum\limits_{i=1}^\ell {(n_i – 1)+1} \right].\]

D. N. Hoover1
1Department of Mathematics and Statistics Queen’s University Kingston, Ontario Canada K7L 5C4
Abstract:

We consider the following three problems: Given a graph \(G\),

  1. What is the smallest number of cliques into which the edges of \(G\) can be partitioned?
  2. How many cliques are needed to cover the edges of \(G\)?
  3. Can the edges of \(G\) be partitioned into maximal cliques of \(G\)?

All three problems are known to be NP-complete for general \(G\). We show here that: (1) is NP-complete for \(\Delta(G) \geq 5\), but can be solved in polynomial time if \(\Delta(G) \leq 4\) (the latter has already been proved by Pullman \([P]\)); (2) is NP-complete for \(\Delta(G) \geq 6\), and polynomial for \(\Delta(G) \leq 5\); (3) is NP-complete for \(\Delta(G) \geq 8\) and polynomial time for \(\Delta(G) \leq 7\).

Wang Zhijian1
1Suzhou Railway Teachers College, Suzhou People’s Republic of China
Abstract:

The total chromatic number \(\chi_2(G)\) of a graph \(G\) is the smallest number of colors which can be assigned to the vertices and edges of \(G\) so that adjacent or incident elements are assigned different colors. For a positive integer \(m\) and the star graph \(K_{1,n}\), the mixed Ramsey number \(\chi_2(m, K_{1,n})\) is the least positive integer \(p\) such that if \(G\) is any graph of order \(p\), either \(\chi_2(G) \geq m\) or the complement \(\overline{G}\) contains \(K_{1,n}\) as a subgraph.
In this paper, we introduce the concept of total chromatic matrix and use it to show the following lower bound: \(\chi_2(m, K_{1,n}) \geq m + n – 2\) for \(m \geq 3\) and \(n \geq 1\). Combining this lower bound with the known upper bound (Fink), we obtain that \(\chi_2(m, K_{1,n}) = m + n – 2\) for \(m\) odd and \(n\) even, and \(m + n – 2 \leq \chi_2(m, K_{1,n}) \leq m + n – 1\) otherwise.

Liang Peiji1, Sun Rongguo2, Ku Tunghsin3, Zhu Lie4
1Association of Science, Fengqiu County 453300, China
2Research Institute of Educational Science, Xining 810000, China
3Hefei Branch of Academia Sinica, Hefei 230031, China
4Suzhou University, Suzhou 215006, China
Abstract:

An addition-multiplication magic square of order \(n\) is an \(n \times n\) matrix whose entries are \(n^2\) distinct positive integers such that not only the sum but also the product of the entries in each row, column, main diagonal, and back diagonal is a constant. It is shown in this paper that such a square exists for any order \(mn\), where \(m\) and \(n\) are positive integers and \(m, n \notin \{1, 2, 3, 6\}\).

A. Gyrfas1, M. S. Jacobson1, L. Kinch, J. Lehel2, R. H. Schelp3
1Research partially supported by ONR grant No. NO0014-85-K-0694.
2Both on leave from Computer and Automation Institute. Hungarian Academy of Sciences, Budapest.
3Research pantially supported by NSF Grant No. DMS-8603717.
Abstract:

A hypergraph is irregular if no two of its vertices have the same degree. It is shown that for all \(r \geq 3\) and \(n \geq r + 3\), there exist irregular \(r\)-uniform hypergraphs of order \(n\). For \(r \geq 6\) it is proved that almost all \(r\)-uniform hypergraphs are irregular. A linear upper bound is given for the irregularity strength of hypergraphs of order \(n\) and fixed rank. Furthermore, the irregularity strength of complete and complete equipartite hypergraphs 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;