
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 092
- Pages: 67-72
- Published: 31/07/2009
We extend and give short proofs of some recent results regarding some classes of rational difference equations.
- Research article
- Full Text
- Ars Combinatoria
- Volume 092
- Pages: 53-65
- Published: 31/07/2009
The skewness \(sk(G)\) of a graph \(G = (V, E)\) is the smallest integer \(sk(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(sk(G)\) edges. The splitting number \(sp(G)\) of \(G\) is the smallest integer \(sp(G) \geq 0\) such that a planar graph can be obtained from \(G\) by \(sp(G)\) vertex splitting operations. The vertex deletion \(vd(G)\) of \(G\) is the smallest integer \(vd(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(vd(G)\) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh \(C_m \times C_n\), for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation \(T_{m,n}\) of \(C_m \times C_n\) in the torus, and an hexagonal mesh \(H_{m,n}\), the dual of \(\mathcal{T}_{C_m\times C_n}\) in the torus. It is established that \(sp(T_{m,n}) = vd(T_{m,n}) = sk(H_{C_m\times C_n}) = sp(\mathcal{H}_{C_m\times C_n}) = vd(\mathcal{H}_{m,n}) = \min\{m,n\}\) and that \(sk(\mathcal{T}_{C_m\times C_n}) = 2\min\{m, n\}\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 092
- Pages: 33-52
- Published: 31/07/2009
Exploiting the empirical observation that the probability of \(k\) fixed points in a Welch-Costas permutation is approximately the same as in a random permutation of the same order, we propose a stochastic model for the most probable maximal number of fixed points in a Welch-Costas permutation.
- Research article
- Full Text
- Ars Combinatoria
- Volume 092
- Pages: 21-31
- Published: 31/07/2009
Let \(\gamma_c(G)\)be the connected domination number of \(G\) and \(\gamma_t(G)\) be the tree domination number of \(G\). In this paper, we study the connected domination number and tree domination of \(P(n,k)\), and show that \(\gamma_{tr}(P(n, 4)) = \gamma_c(P(n, 4)) = n-1\) for \(n \geq 17\), \(\gamma_{tr}(P(n, 6)) = \gamma_c(P(n, 6)) = n-1\) for \(n \geq 25\), and \(\gamma_{tr}(P(n,8)) = \gamma_c(P(n,8)) = n-1\) for \(n \geq 33\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 092
- Pages: 11-19
- Published: 31/07/2009
A cut \((A, B)\) (where \(B = V – A\)) in a graph \(G = (V, E)\) is called internal if and only if there exists a vertex \(x \in A\) that is not adjacent to any vertex in \(B\) and there exists a vertex \(y \in B\) such that it is not adjacent to any vertex in \(A\). In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut \((A, B)\) in a chordal graph \(G\), there exists a clique with \(\kappa(G) + 1\) vertices (where \(\kappa(G)\) is the vertex connectivity of \(G\)) such that it is (approximately) bisected by the cut \((A, B)\). In fact, we give a stronger result: For any internal cut \((A, B)\) of a chordal graph, and for each \(i\), \(0 \leq i \leq \kappa(G) + 1\), there exists a clique \(K_i\) such that \(|A \cap K_i| = \kappa(G) + 1\), \(|A \cap K_i| = i\), and \(|B \cap K_i| = \kappa(G) + 1- i\).
An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be \(\Omega(k^2)\) where \(\kappa(G)\). Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least \(\frac{\kappa(G)(\kappa(G) + 1)}{2}\), where \(\kappa(G)\) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to \(\kappa(G)\). This result is tight.
- Research article
- Full Text
- Ars Combinatoria
- Volume 092
- Pages: 3-9
- Published: 31/07/2009
We determine the automorphism group and the spectrum of the folded hypercube. In addition, we define the Bi-folded hypercube and determine its spectrum.
- Research article
- Full Text
- Ars Combinatoria
- Volume 091
- Pages: 459-465
- Published: 30/04/2009
A connected graph \(G\) is said to be odd path extendable if for any odd path \(P\) of \(G\), the graph \(G – V(P)\) contains a perfect matching. In this paper, we at first time introduce the concept of odd path extendable graphs. Some simple necessary and sufficient conditions for a graph to be odd path extendable are given. In particular, we show that if a graph is odd path extendable, it is hamiltonian.
- Research article
- Full Text
- Ars Combinatoria
- Volume 091
- Pages: 447-458
- Published: 30/04/2009
In this paper, we give one construction for constructing large harmonious graphs from smaller ones. Subsequently, three families of graphs are introduced and some members of them are shown to be or not to be harmonious.
- Research article
- Full Text
- Ars Combinatoria
- Volume 091
- Pages: 439-446
- Published: 30/04/2009
A graph is called set reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. We prove that all graphs are set reconstructible if all \(2\)-connected graphs \(G\) with \(diam(G) = 2\) and all \(2\)-connected graphs \(G\) with \(diam(G) = diam(\overline{G}) = 3\) are set reconstructible.
- Research article
- Full Text
- Ars Combinatoria
- Volume 091
- Pages: 429-438
- Published: 30/04/2009
A function \(f: V(G) \to \{-1,0,1\}\) defined on the vertices of a graph \(G\) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every \(v \in V\), \(f(N(v)) \geq 1\), where \(N(v)\) consists of every vertex adjacent to \(v\). The weight of a MTDF is the sum of its function values over all vertices. A MTDF \(f\) is minimal if there does not exist a MTDF \(g: V(G) \to \{-1,0,1\}\), \(f \neq g\), for which \(g(v) \leq f(v)\) for every \(v \in V\). The upper minus total domination number, denoted by \(\Gamma^{-}_{t}(G)\), of \(G\) is the maximum weight of a minimal MTDF on \(G\). A function \(f: V(G) \to \{-1,1\}\) defined on the vertices of a graph \(G\) is a signed total dominating function (STDF) if the sum of its function values over any open neighborhood is at least one. The signed total domination number, denoted by \(\gamma^{s}_{t}(G)\), of \(G\) is the minimum weight of a STDF on \(G\). In this paper, we establish an upper bound on \(\Gamma^{-}_{t}(G)\) of the 5-regular graph and characterize the extremal graphs attaining the upper bound. Also, we exhibit an infinite family of cubic graphs in which the difference \(\Gamma^{-}_t(G) – \gamma^{s}_t(G)\) can be made arbitrarily large.