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.

Edward Spence1
1 Department of Mathematics, University of Glasgow, Glasgow Gi2 8QQ, Scotland
Abstract:

In a previous paper [2] it was established that, up to isomorphism, there exist at least 112,000 symmetric \(2-(41,16,6)\) designs with a non-trivial automorphism of odd order. Using the underlying derived designs of just one of these and extending them to a \(2-(41,16,6)\) design we have found ten non-isomorphic symmetric \(2-(41,16,6)\) designs with trivial automorphism group (five pairs of non-selfdual designs).

E.J. Cockayne1, G. Fricke2, S.T. Hedetniemi3, C.M. Mynhardt4
1University of Victoria, BC, Canada
2Wright State University, Dayton, Ohio, USA
3Clemson University, SC, USA
4 University of South Africa, RSA
Abstract:

A dominating function for a graph is a function from its vertex set into the unit interval so that the sum of function values taken ‘over the closed neighbourhood of each vertex is at least one. We prove that any graph has a positive minimal dominating function and begin an investigation of the question: When are convex combinations of minimal dominating functions themselves minimal dominating?

A.S. Asratian1
1 Department of Applied Mathematics University of Twente P.O, Box 217, Enschede The Netherlands
Abstract:

The author and N.K. Khachatrian proved that a connected graph \(G\) of order at least \(3\) is hamiltonian if for each vertex \(x\) the subgraph \(G_1(x)\) induced by \(x\) and its neighbors in \(G\) is an Ore graph.

We prove here that a graph \(G\) satisfying the above conditions is fully cycle extendible. Moreover, \(G\) is panconnected if and only if \(G\) is \(3\)-connected and \(G \neq K_n \lor \overline{K}_n\) for some \(n \geq 3\), where \(\lor\) is the join operation. The paper is concluded with two conjectures.

Tan Anderson1, Norman J.Finizio2
1Department of Mathematics University of Glasgow Glasgow, Scotland G12 8QW
2Department of Mathematics University of Rhode Island Kingston, RI 02881
Abstract:

Let \(p,q\) denote primes, \(p \equiv 1 \pmod{4}\), \(g \equiv 3 \pmod{4}\), \(g \geq 7\). In an earlier study we established that if \(\gcd(q-1, p^{n-1}(p-1)) = 2\) and if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) exists for all \(n \geq 0\). Here we consider \(\gcd(qg-1,p^{n-1}(p-1)) > 2\) and prove that if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then there exists a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) for all \(n \geq 0\). The proof employed depends on the existence of an appropriate primitive root of \(p\). Utilizing a theorem of S. D. Cohen we establish that such appropriate primitive roots always exist.

Denise Sakai Troxell1
1 Department of Mathematics and Computer Science Montclair State University Upper Montclair, NJ 07043
Abstract:

A 2-distant coloring of a graph is an assignment of positive integers to its vertices so that adjacent vertices cannot get either the same number or consecutive numbers. Given a 2-distant coloring of a graph \(G\), a hole of \(f\) is a finite maximal set of consecutive integers not used by \(f\), and \(h(f)\) is the number of holes of \(f\). In this paper we study the problem of minimizing the number of holes, i.e., we are interested in the number \(h(G) = \min_f h(f)\) where the minimum runs over all 2-distant colorings \(f\) of \(G\). Besides finding exact values for \(h(G)\) for particular graphs, we also relate \(h(G)\) to the path-covering number and the Hamiltonian completion number of \(G\).

D.K. Garnick1, N.A. Nieuwejaar2
1Department of Computer Science Bowdoin College Brunswick, ME 04011 U.S.A.
2Department of Mathematics and Computer Science Dartmouth College Hanover, NH 03755 U.S.A.
Abstract:

For graph \(G\), a total dominating set \(S\) is a subset of the vertices in \(G\) such that every vertex in \(G\) is adjacent to at least one vertex in \(S\). The total domination number of \(G\) is the cardinality of a smallest total dominating set of \(G\). We consider the total domination number of graphs formed from an \(m\times n\) chessboard by letting vertices represent the squares, and letting two vertices be adjacent if a given chess piece can move between the associated squares. In particular, we bound from above and below the total domination numbers of the graphs induced by the movement of kings, knights, and crosses (a hypothetical piece that moves as does a king, except that it cannot move diagonally). We also provide some results of computer searches for the total domination numbers of small square boards.

W.D. Wallis1, Wan-Di Wei2
1 Department of Mathematics Southern Illinois University Carbondale, IL 62901
2Department of Mathematics Sichuan University Chengdu PR. of China 610064
Abstract:

A set of integers is \(k\)-multiple-free if it never contains two integers \(x\) and \(kx\), where \(k\) is a given integer greater than \(1\). Such a set \(S\) is maximal in \([1,n] = \{1,2,\dots,n\}\) if \(S \cup \{t\}\) is not \(k\)-multiple free for any \(t\) in \([1,n] \setminus S\). In this paper we investigate the size of maximal \(k\)-multiple-free subsets of \([1,n]\), prove that the smallest such set has \(\frac{(k^5-k^3+1)n}{k(k+1)(k^3-1)}+ 0(\log n)\) members, and show that given \(k\) and \(n\), if \(s\) is any integer between the minimum and maximum possible orders, there is a maximal \(k\)-multiple-free subset of \([1,n]\) with \(s\) elements.

LUTZ VOLKMANN1
1Leurstust IE FOR MATHEMATIK, RWTH AACHEN, TEMPLERGRABEN 55, 5100 ‘ AACHEN, GERMANY
Abstract:

Let \(G\) be a simple graph. A set \(D\) of vertices of \(G\) is dominating if every vertex not in \(D\) is adjacent to some vertex in \(D\). A set \(M\) of edges of \(G\) is called independent, or a matching, if no two edges of \(M\) are adjacent in \(G\). The domination number \(\gamma(G)\) is the minimum order of a dominating set in \(G\). The edge independence number \(\alpha_0(G)\) is the maximum size of a matching in \(G\). If \(G\) has no isolated vertices, then the inequality \(\gamma(G) \leq \alpha_0(G)\) holds. In this paper we characterize regular graphs, unicyclic graphs, block graphs, and locally connected graphs for which \(\gamma(G) = \alpha_0(G)\).

Gerd H.Fricke1, T. Hedetniemi2, A. Henning3
1 Wright State University Stephen
2 Clemson University Michael
3University of Natal, Pietermaritzburg
Abstract:

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(I_n\) of vertices of \(G\) is \(n\)-independent if the distance between every two vertices of \(I_n\) is at least \(n+1\). Furthermore, \(I_n\) is defined to be an \(n\)-independent dominating set of \(G\) if \(I_n\) is an \(n\)-independent set in \(G\) and every vertex in \(V(G) – I_nv is at distance at most \(n\) from some vertex in \(I_n\). The \(n\)-independent domination number, \(i_n(G)\), is the minimum cardinality among all \(n\)-independent dominating sets of \(G\). Hence \(i_n(G) = i(G)\) where \(i(G)\) is the independent domination number of \(G\). We establish the existence of a connected graph \(G\) every spanning tree \(T\) of which is such that \(i_n(T) < i_n(G)\). For \(n \in \{1,2\}\) we show that, for any tree \(T\) and any tree \(T’\) obtained from \(T\) by joining a new vertex to some vertex of \(T\), we have \(i_n(T) \geq i_n(T’)\). However, we show that this is not true for \(n \geq 3\). We show that the decision problem corresponding to the problem of computing \(i_n(G)\) is NP-complete, even when restricted to bipartite graphs. Finally, we obtain a sharp lower bound on \(i_n(G)\) for a graph \(G\).

A.H. Baartmans1, Cantian Lin2, W.D. Wallis 3
1Department of Mathematical Sciences, Michigan Technological University, Houghton, MI 49931
2Department of Mathematical Sciences, University of Nevada, Las Vegas, Las Vegas, NV 89154
3Department of Mathematics, Southern Illinois University, Carbondale, IL 62901- 4408
Abstract:

In this paper, we consider symmetric and skew equivalence of Hadamard matrices of order \(28\) and present some computational results and some applications.

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;