
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.
Information Menu
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 193-212
- Published: 30/04/2007
Let \(L\) and \(R\) be two graphs. For any positive integer \(n\), the Ehrenfeucht-Fraissé game \(G_n(L, R)\) is played as follows: on the \(i\)-th move, with \(1 \leq i \leq n\), 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 \(l_i\) be the vertex of \(L\) chosen on the \(i^{th}\) move, and let \(r_i\) be the vertex of \(R\) chosen on the \(i^{th}\) move. The second player wins the game iff the induced subgraphs \(L\{l_1,l_2,…,l_n\}\) and \(R\{r_1,r_2,…,r_n\}\) are isomorphic under the mapping sending \(l_i\) to \(r_i\). 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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 179-191
- Published: 30/04/2007
By applying the method of generating function, the purpose of this paper is to give several summations of reciprocals related to \(l-th\) power of generalized Fibonacci sequences. As applications, some identities involving Fibonacci, Lucas numbers are obtained.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 169-177
- Published: 30/04/2007
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 161-167
- Published: 30/04/2007
Let \(G_{n,m} = C_n \times P_m\), be the cartesian product of an \(n\)-cycle \(C_n\) and a path \(P_m\) of length \(m-1\). We prove that \(\chi'(G_{n,m}) = \chi'(G_{n,m}) = 4\) if \(m \geq 3\), which implies that the list-edge-coloring conjecture (LLECC) holds for all graphs \(G_{n,m}\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 145-160
- Published: 30/04/2007
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(n – 1)/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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 129-144
- Published: 30/04/2007
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\).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 083
- Pages: 101-127
- Published: 30/04/2007
Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\text{exp}_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1,v_2,\ldots ,v_n\}\). The vertices of \(V\) can be ordered so that \(\text{exp}_D(v_{i_1}) \leq \text{exp}_D(v_{i_2}) \leq \ldots \leq \text{exp}_D(v_{i_n})\). The number \(\text{exp}_D(v_{i_k})\) is called \(k\)-exponent of \(D\), denoted by \(\text{exp}_D(k)\). In this paper, we completely characterize \(1\)-exponent set of primitive, minimally strong digraphs with \(n\) vertices.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 93-99
- Published: 30/04/2007
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 47-63
- Published: 30/04/2007
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) \leq n + s(n – 8)\), 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
\[
\exp_D(k) \leq \begin{cases}
k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\
k + s(n-3), & \text{if } s+1 \leq k \leq n,\\
\end{cases} \\.
\]
with equality if and only if \(D\) isomorphic to the diagraph \(D_{s,n}\) with vertex set \(V(D_{s,n})=\{v_1,v_2,\ldots,v_n\}\) and arc set \(E(D_{s,n})=\{(v_i,v_{i+1}):1\leq i\leq n-1\}\cap \{(v_s,v_1),(v_n,v_2)\}\). If \((s,n-1)\neq 1\),then
\[
\exp_D(k)< \begin{cases}
k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\
k + s(n-3), & \text{if } s+1 \leq k \leq n,
\end{cases} \\
\]
and if \((s,n-1)=1\), then \(D_{s, n}\) is a primitive, minimally strong digraph on \(n\) vertices with the \(k\)-exponent
\[
\exp_D(k)= \begin{cases}
k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\
k + s(n-3), & \text{if } s+1 \leq k \leq n,
\end{cases} \\
\]
Moreover, we provide a new proof of Theorem \(1\) in \([6]\) and Theorem \(2\) in \([14]\) by applying this result.
- Research article
- Full Text
- Ars Combinatoria
- Volume 083
- Pages: 65-92
- Published: 30/04/2007
Given a finite projective plane of order \(n\). A quadrangle consists of four points \(A, B, C, D\), no three collinear. If the diagonal points are non-collinear, the quadrangle is called a non-Fano quad. A general sum of squares theorem is proved for the distribution of points in a plane containing a non-Fano quad, whenever \(n \geq 7\). The theorem implies that the number of possible distributions of points in a plane of order \(n\) is bounded for all \(n \geq 7\). This is used to give a simple combinatorial proof of the uniqueness of \(PP(7)\).