
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 087
- Pages: 337-351
- Published: 30/04/2008
A set \(S\) of vertices in a graph \(G = (V, E)\) is a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \setminus S\). The graph \(G\) is called restrained domination excellent if every vertex belongs to some minimum restrained dominating set of \(G\). We provide a characterization of restrained domination excellent trees.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 321-336
- Published: 30/04/2008
In this paper, \(q\)-analogues of the Pascal matrix and the symmetric Pascal matrix are studied. It is shown that the \(q\)-Pascal matrix \(\mathcal{P}_n\) can be factorized by special matrices and the symmetric \(q\)-Pascal matrix \(\mathcal{Q}_n\) has the LDU-factorization and the Cholesky factorization. As byproducts, some \(q\)-binomial identities are produced by linear algebra. Furthermore, these matrices are generalized in one or two variables, where a short formula for all powers of \(q\)-Pascal functional matrix \(\mathcal{P}_n[x]\) is given. Finally, it is similar to Pascal functional matrix, we have the exponential form for \(q\)-Pascal functional matrix.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 291-320
- Published: 30/04/2008
We view a lobster in this paper as below. A lobster with diameter at least five has a unique path \(H = x_0, x_1, \ldots, x_m\) with the property that, besides the adjacencies in \(H\), both \(x_0\) and \(x_m\) are adjacent to the centers of at least one \(K_{i,s}\), where \(s > 0\), and each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 0\). This unique path \(H\) is called the central path of the lobster. We call \(K_{1,s}\) an even branch if \(s\) is nonzero even, an odd branch if \(s\) is odd, and a pendant branch if \(s = 0\). In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex \(x_i\), \(0 \leq i \leq m-1\), is even and the degree of \(x_m\) may be odd or even, and we have one of the following features:
- For some \(t_1, t_2, t_3\), \(0 \leq t_1 < t_2 < t_3 \leq m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(z_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to all three types of branches; each \(x_i\), \(t_2 + 1 \leq i \leq t_3\), is attached to two types of branches; and if \(t_3 < m\) then each \(z_i\), \(t_3 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
- For some \(t_1, t_2\), \(0 < t_1 < t_2 < m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(x_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to two, or all three types of branches; and if \(t_2 < m\) then each \(x_i\), \(t_2 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
- For some \(t\), \(0 \leq t \leq m\), each \(x_i\), \(0 \leq i \leq t\), is attached to all three types of branches; and if \(t < m\) then each \(x_i\), \(t + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 271-290
- Published: 30/04/2008
In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 263-269
- Published: 30/04/2008
A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k;g)\)-cage is a \((k;g)\)-graph with the least number of vertices. In this note, we show that a \((k;g)\)-cage has an \(r\)-factor of girth at least \(g\) containing or avoiding a given edge for all \(r\), \(1 \leq r \leq k-1\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 257-261
- Published: 30/04/2008
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 235-255
- Published: 30/04/2008
This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 225-233
- Published: 30/04/2008
It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS\((p, q, \lambda, \delta)\) graph as a connected, separable graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers \((a, b, c, d)\) is called CS\((p, q, \lambda, \delta)\) realizable if there is a CS\((p, q, \lambda, \delta)\) graph with \(p = a\), \(q = b\), \(\lambda = c\) and \(\delta = d\). Necessary and sufficient conditions for a quadruple to be CS\((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 213-223
- Published: 30/04/2008
An incidence graph of a given graph \(G\), denoted by \(I(G)\), has its own vertex set \(V(I(G)) = \{(ve) | v \in V(G), e \in E(G) \text{ and } v \text{ is incident to } e \text{ in } G\}\) such that the pair \(((ue)(vf))\) of vertices \((ue) (vf) \in V(I(G))\) is an edge of \(I(G)\) if and only if there exists at least one case of \(u = v, e = f, uv = e\) or \(uv = f\). In this paper, we carry out a constructive definition on incidence graphs, and investigate some properties of incidence graphs and some edge-colorings on several classes of them.
- Research article
- Full Text
- Ars Combinatoria
- Volume 087
- Pages: 193-203
- Published: 30/04/2008
The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered for \(m \geq \lceil n^2/4 \rceil\). We thus extend results known for \(m \geq n\lfloor n/3 \rfloor\). When \(n\) is even, all of the values are determined. When \(n\) is odd, some values are determined, and the difficulties are discussed, leaving open questions.