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.

Zheng Wenping1,2, Lin Xiaohui3, Yang Yuansheng3, Yang Gui1,2
1Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,
2School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, P. R. China
3Department of Computer Science, Dalian University of Technology, Dalian, 116024, P. R. China
Abstract:

Let \(P_n\) be a path with \(n\) vertices. \(P_n^k\), the \(k\)-th power of the path \(P_n\), is a graph on the same vertex set as \(P_n\), and the edges that join all vertices \(x\) and \(y\) if and only if the distance between them is at most \(k\). In this paper, the crossing numbers of \(P_n^k\) are studied. Drawings of \(P_n^k\) are presented and proved to be optimal for the case \(n \leq 8\) and for the case \(k \leq 4\).

D. Garijo 1, A. Marquez1, M.P. Revuelta1
1Dep. Matematica Aplicada I. Universidad de Sevilla (Spain).
Abstract:

A graph is said to be locally grid if the structure around each of its vertices is a \(3 x 3\) grid. As a follow up of the research initiated in \([8]\) and \([9]\) we prove that most locally grid graphs are uniquely determined by their Tutte polynomial.

G.C. Lau1,2,3, Y.H. Peng4,4
1Faculty of I. T. and Quantitative Science Universiti Teknologi MARA (Segamat Campus) 85010 Johor, Malaysia
2Department of Mathematics, and “Institute for Mathematical Research
3Institute for Mathematical Research Universiti Putra Malaysia 43400 UPM Serdang, Malaysia
4Department of Mathematics, and “Institute for Mathematical Research Universiti Putra Malaysia 43400 UPM Serdang, Malaysia
Abstract:

Let \(P(G, \lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H, \lambda) = P(G, \lambda)\) implies \(H\) is isomorphic to \(G\). In his Ph.D. thesis, Zhao [Theorems 5.4.2 and 5.4.3] proved that for any positive integer \(t \geq 3\), the complete \(t\)-partite graphs \(K(p – k, p, p, \ldots, p)\) with \(p \geq k+2 \geq 4\) and \(K(p-k, p – 1, p, \ldots, p)\) with \(p \geq 2k \geq 4\) are chromatically unique. In this paper, by expanding the technique employed by Zhao, we prove that the complete \(t\)-partite graph \(K(p-k,\underbrace{ p -1, \ldots, p-1}, \underbrace{p, \ldots, p})\) is chromatically unique for integers \(p \geq k+2 \geq 4\) and \(t \geq d+3 \geq 3\).

Marvin Minei1, Howard Skogman2
1Department of Mathematics University of California Irvine, CA 92697 — 3875
2Department of Mathematics State University of New York College at Brockport Brockport, NY 14420 — 2914
Abstract:

We present a block diagonalization method for the adjacency matrices of two types of covering graphs. A graph \(Y\) is a covering graph of a base graph \(X\) if there exists an onto graph map \(\pi: Y \to X\) such that for each \(x \in X\) and for each \(y \in \{y \mid \pi(y) = x\}\), the collection of vertices adjacent to \(y\) maps onto the collection of vertices adjacent to \(x \in X\). The block diagonalization method requires the irreducible representations of the Galois group of \(Y\) over \(X\). The first type of covering graph is the Cayley graph over the finite ring \(\mathbb{Z}/p^n\mathbb{Z}\). The second type of covering graph resembles large lattices with vertices \(\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\) for large \(n\). For one lattice, the block diagonalization method allows us to obtain explicit formulas for the eigenvalues of its adjacency matrix. We use these formulas to analyze the distribution of its eigenvalues. For another lattice, the block diagonalization method allows us to find non-trivial bounds on its eigenvalues.

Bostjan Bresar1, Simon Spacapan2
1University of Maribor, FEECS Smetanova 17, 2000 Maribor, Slovenia
2University of Maribor, FME Smetanova 17, 2000 Maribor, Slovenia
Abstract:

Broadcast domination in graphs is a variation of domination in which different integer weights are allowed on vertices and a vertex with weight \(k\) dominates its distance \(k\)-neighborhood. A distribution of weights on vertices of a graph \(G\) is called a dominating broadcast, if every vertex is dominated by some vertex with positive weight. The broadcast domination number \(\gamma_b(G)\) of a graph \(G\) is the minimum weight (the sum of weights over all vertices) of a dominating broadcast of \(G\). In this paper, we prove that for a connected graph \(G\), \(\gamma_b(G) \geq \lceil{2\text{rad}(G)}/{3}\rceil\). This general bound and a newly introduced concept of condensed dominating broadcast are used in obtaining sharp upper bounds for broadcast domination numbers of three standard graph products in terms of broadcast domination numbers of factors. A lower bound for a broadcast domination number of the Cartesian product of graphs is also determined, and graphs that attain it are characterized. Finally, as an application of these results, we determine exact broadcast domination numbers of Hamming graphs and Cartesian products of cycles.

G. Araujo-Pardo1, C. Balbuena2, M. Olsen3
1Instituto de Matematicas Universidad Nacional Autonédma de México Ciudad Universitaria, México D.F. 04510, MEXICO.
2Departament de Matematica Aplicada III Universitat Politécnica de Catalunya Campus Nord, Edifici C2, C/ Jordi Girona 1 i 3 E-08034 Barcelona, SPAIN.
3Departamento de Matematicas Aplicadas y Sistemas Universidad Auténoma Metropolitana Unidad Cuajimalpa, MEXICO
Abstract:

The semigirth \(\gamma\) of a digraph \(D\) is a parameter related to the number of shortest paths in \(D\). In particular, if \(G\) is a graph, the semigirth of the associated symmetric digraph \(G^*\) is \(\ell(G^*) = \lfloor {g(G) – 1}/{2} \rfloor\), where \(g(G)\) is the girth of the graph \(G\). In this paper, some bounds for the minimum number of vertices of a \(k\)-regular digraph \(D\) having girth \(g\) and semigirth \(\ell\), denoted by \(n(k, g; \ell)\), are obtained. Moreover, we construct a family of digraphs which achieve the lower bound for some particular values of the parameters.

R. Lakshmi 1, P. Paulraja1
1Department of Mathematics Annamalai University Annamalainagar – 608 002 Tamilnadu, India.
Abstract:

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of all strong orientations of \(G\). Define the orientation number of \(G\), \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\), where \(d(D)\) denotes the diameter of the digraph \(D\). In this paper, it has been shown that \(\overrightarrow{d}(G \times H) = d(G)\), where \(\times\) denotes the tensor product of graphs, \(H\) is a special type of circulant graph, and the diameter, \(d(G)\), of \(G\) is at least \(4\). Some interesting results have been obtained using this result. Further, it is shown that \(d(P_r \times K_s) = d(P_r)\) for suitable \(r\) and \(s\). Moreover, it is proved that \(\overrightarrow{d}(C_r \times K_s) = d(C_r)\) for appropriate \(r\) and \(s\).

Abstract:

We consider some partitions where even parts appear twice and some where evens do not repeat. Further, we offer a new partition theoretic interpretation of two mock theta functions of order \(8\).

Adel T.Diab1
1Faculty of Science, Department of Mathematics, Ain Shams University Abbassia, Cairo, Egypt.
Abstract:

A graph is said to be cordial if it has a \(0-1\) labeling that satisfies certain properties. The purpose of this paper is to generalize some known theorems and results of cordial graphs. Specifically, we show that certain combinations of paths, cycles, and stars are cordial.

G. Santhosh1
1Department of Mathematics Sree Narayana College Neduvarumeode. P. O – 689508 Chengannur, Kerala, INDIA
Abstract:

An edge-magic total labeling on a graph with \(p\) vertices and \(q\) edges is defined as a one-to-one map taking the vertices and edges onto the integers \(1, 2, \ldots, p+q\) with the property that the sum of the labels on an edge and of its endpoints is constant, independent of the choice of edge. The magic strength of a graph \(G\), denoted by \(emt(G)\), is defined as the minimum of all constants over all edge-magic total labelings of \(G\). The maximum magic strength of a graph \(G\), denoted by \(eMt(G)\), is defined as the maximum constant over all edge-magic total labelings of \(G\). A graph \(G\) is called weak magic if \(eMt(G) – emt(G) > p\). In this paper, we study some classes of weak magic graphs.

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;