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.

Xue-Feng Li1
1Department of Applied Mathematics and Physics Xi’an Institute of Post and Telecom Xi’ an 710121, China
Abstract:

Let \(P(G; \lambda)\) denote the chromatic polynomial of a graph \(G\), expressed in the variable \(\lambda\). Then \(G\) is said to be chromatically unique if \(G\) is isomorphic with \(H\) for any graph \(H\) such that \(P(H; \lambda) = P(G; \lambda)\). The graph consisting of \(s\) edge-disjoint paths joining two vertices is called an \(s\)-bridge graph. In this paper, we provide a new family of chromatically unique \(5\)-bridge graphs.

Emrah Kilic1, Nurettin Irmak2
1TOBB Economics anD TECHNOLOGY UNIVERSITY MATEHEMTICS DEPARTMENT, 06560 SocuTozt ANKARA TURKEY
2NIGDE UNIVERSITY MATHEMATICS DEPARTMENT, 51241 NIGDE TURKIYE
Abstract:

Recently in \([5]\), the author considered certain reciprocal sums of general second order recurrence \(\{W_n\}\). In this paper, we generalize the results of Xi and we give some new results for the reciprocal sums of \(k\)-th power of general second order recurrence \(\{W_{kn}\}\) for arbitrary positive integer \(k\).

Weiping Wang1, Tianming Wang1,2
1Department of Applied Mathematics, Dalian University of Technology Dalian 116024, P.R.China
2Department of Mathematics, Hainan Normal University Haikou 571158, P.R.China
Abstract:

In this article, we study the generalized Bernoulli and Euler polynomials, and obtain relationships between them, based upon the technique of matrix representation.

Qingde Kang1, Hongtao Zhao1, Chunping Ma2
1Institute of Mathematics Hebei Normal University Shijiazhuang 050016, P. R. China
2Department of Applied Mathematics North China Electric Power University Baoding 071003, P. R. China
Abstract:

Let \(K_v\) be the complete graph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-decomposition of \(K_v\), denoted by \(G\)-GD\((v)\), is a pair \((X, \mathcal{B})\) where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, nine graphs \(G_i\) with six vertices and nine edges are discussed, and the existence of \(G_i\)-decompositions are completely solved, \(1 \leq i \leq 9\).

Yufa Shen1,2, Yanning Wang3, Wenjie He3, Yongqiang Zhao1,4
1Department of Mathematics, Hebei Normal University, Shijiazhuang 050016, P.R. China
2Department of Mathematics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
3 Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, P.R.China
4Department of Mathematics, Shijiazhuang Normal College, Shijiazhuang 050801, P.R. China
Abstract:

A graph \(G\) is called \({uniquely\; k-list \;colorable}\), or \(UkLC\) for short, if it admits a \(k\)-list assignment \(L\) such that \(G\) has a unique \(L\)-coloring. A graph \(G\) is said to have the property \(M(k)\) (M for Marshal Hall) if and only if it is not \(UkLC\). In \(1999\), M. Ghebleh and E.S. Mahmoodian characterized the \(U3LC\) graphs for complete multipartite graphs except for nine graphs. At the same time, for the nine exempted graphs, they give an open problem: verify the property \(M(3)\) for the graphs \(K_{2,2,\ldots,2}\) for \(r = 4,5,\ldots,8\), \(K_{2,3,4}\), \(K_{1*4,4}\), \(K_{1*4,4}\), and \(K_{1*5,4}\). Until now, except for \(K_{1*5,4}\), the other eight graphs have been showed to have the property \(M(3)\) by W. He et al. In this paper, we show that graph \(K_{1*5,4}\) has the property \(M(3)\), and as consequences, \(K_{1*4,4}\), \(K_{2,2,4}\) have the property \(M(3)\). Therefore the \(U3LC\) complete multipartite graphs are completely characterized.

Glenn G.Chappell1, John Gimbel2, Chris Hartman1
1Department of Computer Science University of Alaska Fairbanks, AK 99775-6670
2Department of Mathematics and Statistics University of Alaska Fairbanks, AK 99775-6660
Abstract:

Given a graph \(G\), we say \(S \subseteq V(G)\) is \({resolving}\) if for each pair of distinct \(u, v \in V(G)\) there is a vertex \(x \in S\) where \(d(u, x) \neq d(v, x)\). The metric dimension of \(G\) is the minimum cardinality of all resolving sets. For \(w \in V(G)\), the distance from \(w\) to \(S\), denoted \(d(w, S)\), is the minimum distance between \(w\) and the vertices of \(S\). Given \(\mathcal{P} = \{P_1, P_2, \ldots, P_k\}\) an ordered partition of \(V(G)\), we say \(P\) is resolving if for each pair of distinct \(u, v \in V(G)\) there is a part \(P_i\) where \(d(u, P_i) \neq d(v, P_i)\). The partition dimension is the minimum order of all resolving partitions. In this paper, we consider relationships between metric dimension, partition dimension, diameter, and other graph parameters. We construct “universal examples” of graphs with given partition dimension, and we use these to provide bounds on various graph parameters based on metric and partition dimensions. We form a construction showing that for all integers \(a\) and \(b\) with \(3 \leq a \leq \beta + 1\), there exists a graph \(G\) with partition dimension \(\alpha\) and metric dimension \(\beta\), answering a question of Chartrand, Salehi, and Zhang \([3]\).

C.N. Campos1, C.P. de Mello1
1Instituto de Computacaéo, UNICAMP, Caixa Postal 6176, 13083-970, Campinas, SP, Brasil.
Abstract:

The total chromatic number \(\chi_\tau(G)\) is the least number of colours needed to colour the vertices and edges of a graph \(G\) such that no incident or adjacent elements (vertices or edges) receive the same colour. This work determines the total chromatic number of grids, particular cases of partial grids, near-ladders, and of \(k\)-dimensional cubes.

Ming-Ju Lee1, Chiang Lin2
1Jen-Teh Junior College of Medicine, Nursing and Management Houlong, Miaoli, Taiwan 356, R.O.C.
2Department of Mathematics National Central University Chung-Li, Taiwan 320, R.O.C.
Abstract:

The \({star arboricity}\) \(sa(G)\) of a graph \(G\) is the minimum number of star forests which are needed to decompose all edges of \(G\). For integers \(k\) and \(n\), \(1 \leq k \leq n\), the \({crown}\) \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : i = 0, 1, \ldots, n-1, j \equiv i+1, i+2, \ldots, i+k \pmod{n}\}\). In \([2]\), Lin et al. conjectured that for every \(k\) and \(n\), \(3 \leq k \leq n-1\), the star arboricity of the crown \(C_{n,k}\) is \(\lceil k/2 \rceil + 1\) if \(k\) is odd and \(\lceil k/2 \rceil + 2\) otherwise. In this note, we show that the above conjecture is not true for the case \(n = 9t\) (\(t\) is a positive integer) and \(k = 4\) by showing that \(sa(C_{9t,4}) = 3\).

Steven Butler1
1Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112, USA
Abstract:

Let \(\mathcal{P}(n,k)\) denote the number of graphs on \(n+k\) vertices that contain \(P_n\), a path on \(n\) vertices, as an induced subgraph. In this note, we will find upper and lower bounds for \(\mathcal{P}(n,k)\). Using these bounds, we show that for \(k\) fixed, \(\mathcal{P}(n,k)\) behaves roughly like an exponential function of \(n\) as \(n\) gets large.

Suzanne M.Seager1
1Mount Saint Vincent University, Halifax, NS, Canada
Abstract:

A \({dominating \;broadcast}\) of a graph \(G\) of diameter \(d\) is a function \(f: V(G) \to \{0, 1, 2, \ldots, d\}\) such that for all \(v \in V(G)\) there exists \(u \in V(G)\) with \(d(u, v) \leq f(u)\). We investigate dominating broadcasts for caterpillars.

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;