Ars Combinatoria

ISSN 0381-7032 (print), 2817-5204 (online)

Ars Combinatoria is the oldest Canadian Journal of Combinatorics, established in 1976. The journal is dedicated to advancing the field of combinatorial mathematics through the publication of high-quality research papers. From 2024 onward, it publishes four volumes per year in March, June, September and December. Ars Combinatoria has gained recognition and visibility in the academic community and is indexed in renowned databases such as MathSciNet, Zentralblatt, and Scopus. The Scope of the journal includes Graph theory, Design theory, Extremal combinatorics, Enumeration, Algebraic combinatorics, Combinatorial optimization, Ramsey theory, Automorphism groups, Coding theory, Finite geometries, Chemical graph theory but not limited.

Qinglin Roger Yu1,2, Zhao Zhang3,4
1Center for Combinatorics, Nankai University Tianjin, 300071, People’s Republic of China
2Department of Mathematics and Statistics, Thompson Rivers University Kamloops, BC, Canada
3College of Mathematics and System Sciences, Xinjiang University Urumai, Xinjiang, 830046, People’s Republic of China
4Department of Mathematics, Zhengzhou University Zhengzhou, Henan, 450052, People’s Republic of China
Abstract:

Let \(G\) be a simple graph and \(f: V(G) \mapsto \{1, 3, 5, \ldots\}\) an odd integer valued function defined on \(V(G)\). A spanning subgraph \(F\) of \(G\) is called a \((1, f)\)-odd factor if \(d_F(v) \in \{1, 3, \ldots, f(v)\}\) for all \(v \in V(G)\), where \(d_F(v)\) is the degree of \(v\) in \(F\). For an odd integer \(k\), if \(f(v) = k\) for all \(v\), then a \((1, f)\)-odd factor is called a \([1, k]\)-odd factor. In this paper, the structure and properties of a graph with a unique \((1, f)\)-odd factor is investigated, and the maximum number of edges in a graph of the given order which has a unique \([1, k]\)-odd factor is determined.

Yuqin Zhang1, Yonghui Fan2
1Department of Mathematics Beijing Institute of Technology, 100081, Beijing, China
2College of Mathematics and Information Science Hebei Normal University, 050016, Shijiazhuang, China
Abstract:

Erdős and Soifer \([3]\) and later Campbell and Staton \([1]\) considered a problem which was a favorite of Erdős \([2]\): Let \(S\) be a unit square. Inscribe \(n\) squares with no common interior point. Denote by \(\{e_1, e_2, \ldots, e_n\}\) the side lengths of these squares. Put \(f(n) = \max \sum\limits_{i=1}^n e_i\). And they discussed the bounds for \(f(n)\). In this paper, we consider its dual problem – covering a unit square with squares.

D. Bauer1, E. Schmeichel2, T. Surowiec1
1Department of Mathematical Sciences Stevens Institute of Technology Hoboken, NJ 07030, U.S.A.
2Department of Mathematics San Jose State University San Jose, CA 95192, U.S.A.
Abstract:

The well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph \(G\) in terms of the deficiency \(\max_{X \subseteq V(G)} \{ \omega_0(G – X) – |X| \}\) of \(G\), where \(\omega_0(H)\) denotes the number of odd components of \(H\). Let \(G’\) be the graph formed from \(G\) by subdividing (possibly repeatedly) a number of its edges. In this note we study the effect such subdivisions have on the difference between the size of a maximum matching in \(G\) and the size of a maximum matching in \(G’\).

Maged Z.Youssef 1, E. A.Elsakhawi1
1Faculty of Science, Ain Shams University Abbassia , Cairo , Egypt.
Abstract:

In this paper, we give some necessary conditions for a prime graph. We also present some new families of prime graphs such as \(K_n \odot K_1\) is prime if and only if \(n \leq 7\), \(K_n \odot \overline{K_2}\) is prime if and only if \(n \leq 16\), and \(K_{m}\bigcup S_n\) is prime if and only if \(\pi(m+n-1) \geq m\). We also show that a prime graph of order greater than or equal to \(20\) has a nonprime complement.

AP Burger1, JH van Vuuren1, WR Grundlingh2
1Department of Logistics, University of Stellenbosch, Private Bag X1, Matieland, 7602, Republic of South Africa,
2Department of Mathematics and Statistics, University of Victoria, PO Box 3045, STN CSC, Victoria, BC V8W 3P4, Canada,
Abstract:

Consider a lottery scheme consisting of randomly selecting a winning \(t\)-set from a universal \(m\)-set, while a player participates in the scheme by purchasing a playing set of any number of \(n\)-sets from the universal set prior to the draw, and is awarded a prize if \(k\) or more elements of the winning \(t\)-set occur in at least one of the player’s \(n\)-sets (\(1 \leq k \leq \{n,t\} \leq m\)). This is called a \(k\)-prize. The player may wish to construct a playing set, called a lottery set, which guarantees the player a \(k\)-prize, no matter which winning \(t\)-set is chosen from the universal set. The cardinality of a smallest lottery set is called the lottery number, denoted by \(L(m,n,t;k)\), and the number of such non-isomorphic sets is called the lottery characterisation number, denoted by \(\eta(m,n,t;k)\). In this paper, an exhaustive search technique is employed to characterise minimal lottery sets of cardinality not exceeding six, within the ranges \(2 \leq k \leq 4\), \(k \leq t \leq 11\), \(k \leq n \leq 12\), and \(\max\{n,t\} \leq m \leq 20\). In the process, \(32\) new lottery numbers are found, and bounds on a further \(31\) lottery numbers are improved. We also provide a theorem that characterises when a minimal lottery set has cardinality two or three. Values for the lottery characterisation number are also derived theoretically for minimal lottery sets of cardinality not exceeding three, as well as a number of growth and decomposition properties for larger lotteries.

M.P. Wasadikar1, S.K. Nimbhorkar2, Lisa Demeyer3
1Department of Mathematics, Dr. B. A. M. University, Aurangabad 431004, India.
2Department of Mathematics, Dr. B. A. M. University, Au- rangabad 431004, India.
3Department of Mathematics, Central Michigan University, Mount Pleas- ant MI, 48858, USA.
Abstract:

Beck’s coloring is studied for meet-semilattices with \(0\). It is shown that for such semilattices, the chromatic number equals the clique number.

Anders Sune Pedersen1, Preben Dahl Vestergaard1
1Department of Mathematics, Aalborg University, Fredrik Bajers Vej 7G, DK 9220 Aalborg, Denmark
Abstract:

The main result of this paper is an upper bound on the number of independent sets in a tree in terms of the order and diameter of the tree. This new upper bound is a refinement of the bound given by Prodinger and Tichy [Fibonacci Q., \(20 (1982), no. 1, 16-21]\). Finally, we give a sufficient condition for the new upper bound to be better than the upper bound given by Brigham, Chandrasekharan and Dutton [Fibonacci Q., \(31 (1993), no. 2, 98-104]\).

Wen-Chung Huang1, Wang-Cheng Yang1
1Department of Mathematics Soochow University, Taipei, Taiwan, Republic of China.
Abstract:

In this paper, it is shown that every extended directed triple system of order \(v\) can be embedded in an extended directed triple system of order \(n\) for all \(n \geq 2v\). This produces a generalization of the Doyen- Wilson theorem for extended directed triple systems.

K. Kayathri1, S.Pethanachi Selvam2
1Department of Mathematics, Thiagarajar College, Madurai-625 009.
2Department of Mathematics, The Standard Fireworks Rajaratnam College for Women, Sivakasi-626 123.
Abstract:

A semigraph \(G\) is an ordered pair \((V,X)\) where \(V\) is a non-empty set whose elements are called vertices of \(G\) and \(X\) is a set of \(n\)-tuples (\(n > 2\)), called edges of \(G\), of distinct vertices satisfying the following conditions:

i) any edge \((v_1, v_2, \ldots, v_n)\) of \(G\) is the same as its reverse \((v_n, v_{n-1}, \ldots, v_1)\),and

ii) any two edges have at most one vertex in common.

Two edges are adjacent if they have a common vertex. \(G\) is edge complete if any two edges in \(G\) are adjacent. In this paper, we enumerate the non-isomorphic edge complete \((p,2)\)semigraphs.

Mohamed H.El-Zahar1, Ramy S.Shaheen2
1Department of Mathematics, Faculty of Science, Ain Shams University, Abbaseia, Cairo, Egypt.
2Department of Mathematics, F aculty of Science, Tishreen University, Lattakia, Syria.
Abstract:

Let \(G = (V, E)\) be a graph. A subset \(D \subseteq V\) is called a dominating set for \(G\) if for every \(v \in V – D\), \(v\) is adjacent to some vertex in \(D\). The domination number \(\gamma(G)\) is equal to \(\min \{|D|: D \text{ is a dominating set of } G\}\).

In this paper, we calculate the domination numbers \(\gamma(C_m \times C_n)\) of the product of two cycles \(C_m\) and \(C_n\) of lengths \(m\) and \(n\) for \(m = 5\) and \(n = 3 \mod 5\), also for \(m = 6, 7\) and arbitrary \(n\).

E-mail Alert

Add your e-mail address to receive upcoming issues of Ars Combinatoria.

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;