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.

Zeev Nutov1, Masao Tsugaki2
1Department of Computer Science The Open University of Israel
2Department of Mathematical Information Science Science University of Tokyo
Abstract:

Let G=(V,E) be a k-connected graph. For t3, a subset TV is a (t,k)-shredder if |T|=k and GT has at least t connected components. It is known that the number of (t,k)-shredders in a k-connected graph on n nodes is less than 2n2t3. We show a slightly better bound for the case k2t3.

Jason Brown1, Richard Hoshino1
1Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia, Canada B3H 3J5
Abstract:

Let L and R be two graphs. For any positive integer n, the Ehrenfeucht-Fraissé game Gn(L,R) is played as follows: on the i-th move, with 1in, the first player chooses a vertex on either L or R, and the second player responds by choosing a vertex on the other graph. Let li be the vertex of L chosen on the ith move, and let ri be the vertex of R chosen on the ith move. The second player wins the game iff the induced subgraphs L{l1,l2,,ln} and R{r1,r2,,rn} are isomorphic under the mapping sending li to ri. It is known that the second player has a winning strategy if and only if the two graphs, viewed as first-order logical structures (with a binary predicate E), are indistinguishable (in the corresponding first-order theory) by sentences of quantifier depth at most n. In this paper we will give the first complete description of when the second player has a winning strategy for L and R being both paths or both cycles. The results significantly improve previous partial results.

Gaowen Xi1
1Department of Mathematics, Luoyang Teachers’ College, Luoyang, 471022, P. R. China
Abstract:

By applying the method of generating function, the purpose of this paper is to give several summations of reciprocals related to lth power of generalized Fibonacci sequences. As applications, some identities involving Fibonacci, Lucas numbers are obtained.

Malgorzata Moczurad1, Wlodzimierz Moczurad1
1Institute of Computer Science, Jagiellonian University Nawojki 11, 30-072 Krakéw, Poland
Abstract:

Bricks are polyominoes with labelled cells. The problem whether a given set of bricks is a code is undecidable in general. We consider sets consisting of square bricks only. We have shown that in this setting, the codicity of small sets (two bricks) is decidable, but 15 bricks are enough to make the problem undecidable. Thus the step from words to even simple shapes changes the algorithmic properties significantly (codicity is easily decidable for words). In the present paper we are interested whether this is reflected by quantitative properties of words and bricks. We use their combinatorial properties to show that the proportion of codes among all sets is asymptotically equal to 1 in both cases.

Guoping Wang1, Qiongxiang Huang1
1The College of Mathematics and Systems Sciences, Xinjiang University, Urumqi, Xinjiang 830046, P.R.China
Abstract:

Let Gn,m=Cn×Pm, be the cartesian product of an n-cycle Cn and a path Pm of length m1. We prove that χ(Gn,m)=χ(Gn,m)=4 if m3, which implies that the list-edge-coloring conjecture (LLECC) holds for all graphs Gn,m.

Nicholas A.Loehr1
1Department of Mathematics University of Pennsylvania Philadelphia, PA 19104
Abstract:

Various authors have defined statistics on Dyck paths that lead to generalizations of the Catalan numbers. Three such statistics are area, maj, and bounce. Haglund, whe introduced the bounce statistic, gave an algebraic proof that n(n1)/2+ area — bounce and maj have the same distribution on Dyck paths of order n. We give an explicit bijective proof of the same result.

Dalibor Froncek 1, Tereza Kovarova2
1Department of Mathematics and Statistics University of Minnesota Duluth 1117 University Drive Duluth, MN 55810 – 3000, U.S.A.
2Department of Mathematics and Descriptive Geometry Technical University of Ostrava 17. listopadu 15 708 33 Ostrava, Czech Republic
Abstract:

We develop a new type of a vertex labeling of graphs, namely 2n-cyclic blended labeling, which is a generalization of some previously known labelings. We prove that a graph with this labeling factorizes the complete graph on 2nk vertices, where k is odd and n,k>1.

Yahui Hu1
1Department of Mathematics, Hunan First Normal College, Changsha 410205, P.R.China
Abstract:

Let D=(V,E) be a primitive digraph. The exponent of D at a vertex uV, denoted by expD(u), is defined to be the least integer k such that there is a walk of length k from u to v for each vV. Let V={v1,v2,,vn}. The vertices of V can be ordered so that expD(vi1)expD(vi2)expD(vin). The number expD(vik) is called k-exponent of D, denoted by expD(k). In this paper, we completely characterize 1-exponent set of primitive, minimally strong digraphs with n vertices.

Iwona Wloch1
1Faculty of Mathematics and Applied Physics Department of Mathematics ul. W. Pola 2,35-959 Rzeszéw, Poland
Abstract:

In [4] H. Galana-Sanchez introduced the concept of kernels by monochromatic paths which generalize the concept of kernels. In [6] they proved the necessary and sufficient conditions for the existence of kernels by monochromatic paths of the duplication of a subset of vertices of a digraph, where a digraph is without monochromatic directed circuits. In this paper we study independent by monochromatic paths sets and kernels by monochromatic paths of the duplication. We generalize result from [6] for an arbitrary edge coloured digraph.

Yahui Hu1, Pingzhi Yuan2, Weijun Liu3
1Department of Mathematics, Hunan First Normal College, Changsha 410205, P.R.China
2Department of Mathematics, Sun Yat-Sen University, Guangzhou 510275, P.R.China
3Department of Mathematics, Central South University, Changsha 410075, P.R.China
Abstract:

Let D=(V,E) be a primitive, minimally strong digraph. In 1982, J. A. Ross studied the exponent of D and obtained that exp(D)n+s(n8), where s is the length of a shortest circuit in D [D]. In this paper, the k-exponent of D is studied. Our principle result is that
expD(k){k+1+s(n3),if 1ks, k+s(n3),if s+1kn,.
with equality if and only if D isomorphic to the diagraph Ds,n with vertex set V(Ds,n)={v1,v2,,vn} and arc set E(Ds,n)={(vi,vi+1):1in1}{(vs,v1),(vn,v2)}. If (s,n1)1,then
expD(k)<{k+1+s(n3),if 1ks, k+s(n3),if s+1kn, and if (s,n1)=1, then Ds,n is a primitive, minimally strong digraph on n vertices with the k-exponent expD(k)={k+1+s(n3),if 1ks, k+s(n3),if s+1kn, Moreover, we provide a new proof of Theorem 1 in [6] and Theorem 2 in [14] by applying this result.

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;