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.

Changqing Xu1, Yanbin Jia1
1Department of Applied Mathematics, Hebei University of Technology, Tianjin 300401, P.R. China
Abstract:

Let \(G\) be a graph with vertex set \(V(G)\). An edge coloring \(C\) of \(G\) is called an edge-cover coloring, if for each color, the edges assigned with it form an edge cover of \(G\). The maximum positive integer \(k\) such that \(G\) has a \(k\)-edge-cover coloring is called the edge cover chromatic index of \(G\) and is denoted by \(\chi’_c(G)\). It is well known that \(\min\{d(v) – \mu(v) : v \in V(G)\} \leq \chi’_c(G) \leq \delta(G)\), where \(\mu(v)\) is the multiplicity of \(v\) and \(\delta(G)\) is the minimum degree of \(G\). If \(\chi’_c(G) = \delta(G)\), \(G\) is called a graph of CI class, otherwise \(G\) is called a graph of CII class. In this paper, we give a new sufficient condition for a nearly bipartite graph to be of CI class.

Ludovit Niepel1, Anton Cerny1, Bader AlBdaiwi1
1Department of Mathematics and Computer Science Kuwait University P.O. Box 5969, Safat , 13060, Kuwait
Abstract:

Though the well-known Vizing’s conjecture is not true for directed graphs in general, we show that it is true when the digraph and its reversal contain an efficient dominating set. In this paper, we investigate the existence of such sets in directed tori and infinite grids. We give a complete characterization of efficient dominating sets in the \(3\)-dimensional case and show the nonexistence of efficient \(d\)-dominating sets in directed tori for any \(d > 1\) and any dimension \(n > 1\).

Lin Dong1, Changhong Lu2,3, Xiao Wang2
1Department of Mathematics, Tongji University, Shanghai, 200092, China
2Department of Mathematics, East China Normal University, Shanghai, 200062, China
3Institute of Theoretical Computing, ECNU, Shanghai, 200062, China
Abstract:

For every two vertices \(u\) and \(v\) in a graph \(G\), a \(u-v\) geodesic is a shortest path between \(u\) and \(v\). Let \(I(u,v)\) denote the set of all vertices lying on a \(u-v\) geodesic. For a vertex subset \(S\), let \(I_G(S)\) denote the union of all \(I_G(u,v)\) for \(u,v \in S\). The geodetic number \(g(G)\) of a graph \(G\) is the minimum cardinality of a set \(S\) with \(I_G(S) = V(G)\). For a digraph \(D\), there is analogous terminology for the geodetic number \(g(D)\). The geodetic spectrum of a graph \(G\), denoted by \(S(G)\), is the set of geodetic numbers over all orientations of graph \(G\). The lower geodetic number is \(g^-(G) = \min S(G)\) and the upper geodetic number is \(g^+(G) = \max S(G)\). The main purpose of this paper is to investigate lower and upper geodetic numbers of graphs. Our main results in this paper are:

  1. For every spanning tree \(T\) of a connected graph \(G\), \(g^-(G) \leq \ell(T)\), where \(\ell(T)\) is the number of leaves of \(T\).
  2. The conjecture \(g^+(G) \geq g(G)\) is true for chordal graphs, triangle-free graphs and \(4\)-colorable graphs.
Stevo Stevic1
1Mathematical Institute of the Serbian Academy of Science, Knez Mihailova 36/III, 11000 Beograd, Serbia
Abstract:

We estimate the essential norm of the weighted composition operator \(uC_{\varphi}\) from the weighted Bergman space \(A^{p}_{\alpha}(\mathbb{B})\) to the weighted space \(H^{\infty}_{\mu}(\mathbb{B})\) on the unit ball \(\mathbb{B}\), when \(p > 1\) and \(\alpha \geq -1\) (for \(\alpha = -1\), \(A^{p}_{\alpha}\) is the Hardy space \(H^{p}(\mathbb{B})\)). We also give a necessary and sufficient condition for the operator \(uC_{\varphi} : A^{p}_{\alpha}(\mathbb{B}) \to H^{\infty}_{\mu}(B)\) to be compact, and for the operator \(uC_{\varphi} : A^{p}_{\alpha}(\mathbb{B}) \to H^{\infty}_{\mu,0}(\mathbb{B})\) to be bounded or compact, when \(p > 0\), \(\alpha \geq -1\).

Mingjing Gao1,2, Erfang Shan3
1Depart. of Math., Hebei Normal University of Science and Technology, Qinhuangdao 066004, Hebei, China
2‘Depart. of Math., Shanghai University, Shanghai 200444, China
3Depart. of Math., Shanghai University, Shanghai 200444, China
Abstract:

Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is called 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 – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\). In this paper, we establish an upper bound on \(\gamma_r(G)\) for a connected graph \(G\) by the probabilistic method.

Harris Kwong1
1Dept. of Math. Sci. SUNY at Fredonia Fredonia, NY 14063, USA
Abstract:

Any vertex labeling \(f: V \to \{0,1\}\) of the graph \(G = (V,E)\) induces a partial edge labeling \(f^*: E \to \{0,1\}\) defined by \(f^*(uv) = f(u)\) if and only if \(f(u) = f(v)\). The balance index set of \(G\) is defined as \(\{|f^{*{-1}}(0) – f^{*{-1}}(1)|: |f^{-1}(0) – f^{-1}(1)| \leq 1\}\). In this paper, we first determine the balance index sets of rooted trees of height not exceeding two, thereby completely settling the problem for trees with diameter at most four. Next we show how to extend the technique to rooted trees of any height, which allows us to derive a method for determining the balance index set of any tree.

J.D. Key1, J. Moori2, B.G. Rodrigues3
1Department of Mathematical Sciences Clemson University Clemson SC 29634, U.S.A.
2School of Mathematical Sciences University of KwaZulu-Natal Pietermaritzburg 3209, South Africa
3School of Mathematical Sciences University of KwaZulu-Natal Durban 4041, South Africa
Abstract:

We show that partial permutation decoding can be used, and give explicit \(s\)-PD-sets in the symmetric group, where \(s\) is less than the full error-correction capability of the code, for some classes of binary codes obtained from the adjacency matrices of the graphs with vertices the \(\binom{n}{3}\) \(3\)-subsets of a set of size \(n\) with adjacency defined by the vertices as \(3\)-sets being adjacent if they have a fixed number of elements in common.

Hong Lin1, Xiaofeng Guo2
1School of Sciences, Jimei University, Xiamen 361021, P. R. China
2School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
Abstract:

Let \(G\) be a simple connected graph. For a subset \(S\) of \(V(G)\) with \(|S| = 2n + 1\), let \(\alpha_{(2n+1)}(G,S)\) denote the graph obtained from \(G\) by contracting \(S\) to a single vertex. The graph \(\alpha_{(2n+1)}(G, S)\) is also said to be obtained from \(G\) by an \(\alpha_{(2n+1)}\)-contraction. For pairwise disjoint subsets \(S_1, S_2, \ldots, S_{2n}\) of \(V(G)\), let \(\beta_n(G, S_1, S_2, \ldots, S_{2n})\) denote the graph obtained from \(G\) by contracting each \(S_i\) (\(i = 1, 2, \ldots, 2n\)) to a single vertex respectively. The graph \(\beta_{2n}(G, S_1, S_2, \ldots, S_{2n})\) is also said to be obtained from \(G\) by a \(\beta_{2n}\)-contraction. In the present paper, based on \(\alpha_{(2n+1)}\)-contraction and \(\beta_{2}\)-contraction, some new characterizations for \(n\)-extendable bipartite graphs are given.

Aygul Mamut1, Sawut Awut2, Elkin Vumar1
1College of Mathematics and System Sciences, Xinjiang University, Urumgi 830046, P.R. China
2Department of Mathematics , Xinjiang Yili Normal College, Yining 835000, P.R. China
Abstract:

A graph \(G\) is quasi-claw-free if it satisfies the property: \(d(x, y) = 2 \Rightarrow\) there exists \(u \in N(x) \cap N(y)\) such that \(N[u] \subseteq N[x] \cup N[y]\). In this paper, we prove that the circumference of a \(2\)-connected quasi-claw-free graph \(G\) on \(n\) vertices is at least \(\min\{3\delta + 2, n\}\) or \(G \in \mathcal{F}\), where \(\mathcal{F}\) is a class of nonhamiltonian graphs of connectivity \(2\). Moreover, we prove that if \(n \leq 40\), then \(G\) is hamiltonian or \(G \in \mathcal{F}\).

Wenwen Sun1
1Department of Mathematics, Shanghai Jiao Tong University Shanghai 200240, P.R.China
Abstract:

Let \(K_{n,n}\) denote the complete bipartite graph with \(n\) vertices in each part. In this paper, it is proved that there is no cyclic \(m\)-cycle system of \(K_{n,n}\) for \(m \equiv 2 \pmod{4}\) and \(n \equiv 2 \pmod{4}\). As a consequence, necessary and sufficient conditions are determined for the existence of cyclic \(m\)-cycle systems of \(K_{n,n}\) for all integers \(m \leq 30\).

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;