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.

Johannes H.Hattingh 1, Michael A.Henning2
1Department of Mathematics and Statistics Georgia State University Atlanta, Georgia 30303, USA
2School of Mathematical Sciences University of KwaZulu-Natal Pietermaritzburg, 3209 South Africa
Abstract:

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.

De-Yin Zheng1,2
1Department of Mathematics, Hangzhou Normal University, Hongzhou 310012, P. R. China
2Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, P. R. China
Abstract:

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.

Pratima Panigrahi1, Debdas Mishra1
1Department of Mathematics Indian Institute of Technology, Kharagpur 721302
Abstract:

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:

  1. 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.
  2. 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.
  3. 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.
T.N. Janakiraman1, M. Bhanumathi2, S. Muthammai2
1Department of Mathematics and Computer Applications National Institute of Technology, Tiruchirapalli Tamil Nadu, India.
2Department of Mathematics Government Arts College for Women, Pudukkottai Tamil Nadu, India.
Abstract:

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.

Guizhen Liu1, Qinglin Yu2,3
1 Department of Mathematics Shandong University at Weihai, Weihai, Shandong, PRC
2Center of Combinatorics, LPMC, Nankai University, Tianjing, PRC
3Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC, Canada
Abstract:

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\).

L.H. Clark1, J.P. McSorley1
1Department of Mathematics Southern Illinois University Carbondale Carbondale, IL 62901-4408
Yueping Li1, Dingjun Lou1, Yunting Lu1
1 DEPARTMENT OF COMPUTER SCIENCE SUN YAT-SEN UNIVERSITY GUANGZHOU 510275, P.R. CHINA
Abstract:

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.

D. DiMarco1
1Neumann College
Abstract:

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.

Zhang Zhong-fu1,2, Yao Bing 2, Li Jing-wen 1, Liu Lin-zhong1, Wang Jian-fang3, Xu Bao-gen4
1Institute of Applied Mathematics, Lanzhou JiaoTong University, Lanzhou, 730070, P.R.China
2College of Mathematics and Information Science, Northwest Normal University, Lanzhou, 730070, P.R.China
3Institute of Applied Mathematics, Chinese Academy of Science, Beijing, 100080, P.R.China
4 Department of Mathematics, East China Jiaotong University, Nanchang 330013, P.R. China
Abstract:

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.

Lynne L.Doty1, Kevin K.Ferland2
1Marist College, Poughkeepsie, NY 12601
2Bloomsburg University, Bloomsburg, PA 17815
Abstract:

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.

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;