Utilitas Algorithmica (UA)

ISSN: xxxx-xxxx (print)

Utilitas Algorithmica (UA) is a premier, open-access international journal dedicated to advancing algorithmic research and its applications. Launched to drive innovation in computer science, UA publishes high-impact theoretical and experimental papers addressing real-world computational challenges. The journal underscores the vital role of efficient algorithm design in navigating the growing complexity of modern applications. Spanning domains such as parallel computing, computational geometry, artificial intelligence, and data structures, UA is a leading venue for groundbreaking algorithmic studies.

Kishore Sinha1, Neelam Sinha2
1Department of Statistics Birsa Agricultural University Ranchi – 834006 India
2Department of Mathematics Indian Institute of Technology Bombay Mumbai, India
Abstract:

A construction of optimal quaternary codes from symmetrical Balanced Incomplete Block (BIB) design \((4t – 1, 2t – 1, t – 1)\) is described.

Zehui Shao1,2, Jin Xu2, Lingiang Pan2
1School of Information Science & Technology, Chengdu University, Chengdu, 610106, China
2Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, China
Abstract:

For integers \(s,t \geq 1\), the Ramsey number \(R(s, t)\) is defined to be the least positive integer \(n\) such that every graph on \(n\) vertices contains either a clique of order \(s\) or an independent set of order \(t\). In this note, we derive new lower bounds for the Ramsey numbers: \(R(6,8) \geq 129\), \(R(7,9) \geq 235\) and \(R(8,17) \geq 937\). The new bounds are obtained with a constructive method proposed by Xu and Xie et al. and the help of computer algorithm.

Jonathan L.Gross1, Imran F.Khan1, Mehvish I.Poshni1
1Department of Computer Science Columbia University, New York, NY 10027
Abstract:

We pursue the problem of counting the imbeddings of a graph in each of the orientable surfaces. We demonstrate how to achieve this for an iterated amalgamation of arbitrarily many copies of any graph whose genus distribution is known and further analyzed into a partitioned genus distribution. We introduce the concept of recombinant strands of face-boundary walks, and we develop the use of multiple production rules for deriving simultaneous recurrences. These two ideas are central to a broad-based approach to calculating genus distributions for graphs synthesized from smaller graphs.

Jun-Ming Xu1, Jian-Wei Wang1, Wei-Wei Wang1
1Department of Mathematics University of Science and Technology of China Hefei, Anhui, 230026, China
Abstract:

The super (resp., edge-) connectivity of a connected graph is the minimum cardinality of a vertex-cut (resp., an edge-cut) whose removal does not isolate a vertex. In this paper, we consider the two parameters for a special class of graphs \(G(G_p,G_1; M)\), proposed by Chen et al [Applied Math. and Computation, \(140 (2003), 245-254]\), obtained from two \(k\)-regular \(k\)-connected graphs \(G_p\) and \(G_1\), with the same order by adding a perfect matching between their vertices. Our results improve ones of Chen et al. As applications, the super connectivity and the super edge-connectivity of the \(n\)-dimensional hypercube, twisted cube, cross cube, Möbius cube and locally twisted cube are all \(2n – 2\).

G.R. Omidi1
1Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, 84156-83111, Iran
Abstract:

We investigate the existence of \(3\)-designs and uniform large sets of \(3\)-designs with block size \(6\) admitting \(\text{PSL}(2, 2^n)\) as an automorphism group.

S.W. Saputro1, E.T. Baskoro1, A.N.M. Salman1, D. Suprijanto1
1Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung (ITB) Jalan Ganesha No. 10 Bandung 40132, Indonesia
Abstract:

A simple graph \( G = (V(G), E(G)) \) admits an \( H \)-covering if every edge in \( E(G) \) belongs to a subgraph of \( G \) that is isomorphic to \( H \). An \((a,d)\)-\( H \)-\({antimagic\; total \;labeling}\) of \( G \) is a bijective function \( \xi : V(G) \cup E(G) \to \{1,2,\dots,|V(G)| + |E(G)|\} \) such that for all subgraphs \( H’ \) isomorphic to \( H \), the \( H \)-weights \( w(H’) = \sum_{v \in V(H’)} \xi(v) + \sum_{e \in E(H’)} \xi(e) \) constitute an arithmetic progression \( a, a+d, a+2d, \dots, a+(t-1)d \), where \( a \) and \( d \) are positive integers and \( t \) is the number of subgraphs of \( G \) isomorphic to \( H \). Additionally, the labeling \( \xi \) is called a \({super}\) \((a, d)\)-\( H \)-\({antimagic\; total\; labeling}\) if \( \xi(V(G)) = \{1, 2, \dots, |V(G)|\} \).

In this paper, we introduce the notion of \((a, d)\)-\( H \)-\({antimagic\; total\; labeling}\) and study some basic properties of such labeling. We provide an example of a family of graphs obtaining the labelings, that is providing \((a, d)\)-cycle-antimagic labelings of fans.

Nur Inayah1, A. N. M. Salman2, R. Simanjuntak2
1Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Jalan Ganesa 10 Bandung 40132, Indonesia
2Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Jalan Ganesa 10 Bandung 40132, Indonesia
Abstract:

Let \( j \geq 2 \) be a natural number. For graphs \( G \) and \( H \), the size multipartite Ramsey number \( m_j(G, H) \) is the smallest natural number \( t \) such that any \( 2 \)-coloring by red and blue on the edges of \( K_{j \times t} \) necessarily forces a red \( G \) or a blue \( H \) as a subgraph. Let \( P_n \) be a path on \( n \) vertices. In this note, we determine the exact value of the size multipartite Ramsey number \( m_j(P_4, P_n) \) for \( n \geq 2 \).

Syafrizal Sy1,2, E.T. Baskoro2, S. Uttunggadewa2, H. Assiyatun2
1 Department of Mathematics, Andalas University Kampus UNAND, Limau Manis Padang 25163, Indonesia
2Combinatorial Mathematics Research Group Institut Teknologi Bandung Ji. Ganesa 10 Bandung 40132, Indonesia
Abstract:

Let \(j \geq 2\) be a natural number. For graphs \(G\) and \(H\), the size multipartite Ramsey number \(m_j(G, H)\) is the smallest natural number \(t\) such that any \(2\)-coloring by red and blue on the edges of \(K_{j \times t}\) necessarily forces a red \(G\) or a blue \(H\) as subgraph. Let \(P_n\) be a path on \(n\) vertices. In this note, we determine the exact value of the size multipartite Ramsey number \(m_j(P_4, P_n)\) for \(n \geq 2\).

Wayan Sudarsana1, E.T. Baskoro1, Hilda Assiyatun1, Saladin Uttunggadewa1
1Combinatorial Mathematics Research Division Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung (ITB) Jalan Ganesha No. 10 Bandung 40132, Indonesia.
Abstract:

In this paper, we determine the Ramsey number for the disjoint union of graphs versus a graph \( H \), especially \( R\left(\bigcup_{i=1}^{k} l_i S_{n_i}(1,1), W_6\right) \), \( R\left(\bigcup_{i=1}^{k} l_i S_{n_i}(1,2), W_6\right) \), and \( R\left(\bigcup_{i=1}^k l_i S_{n_i}, W_4\right) \).

Saib Suwilo1
1Department of Mathematics University of Sumatera Utara Medan 20155 Indonesia, saibQusu.ac.id
Abstract:

In this paper, we discuss an upper bound for exponents of loopless asymmetric two-colored digraphs. If \( D \) is an asymmetric primitive two-colored digraph on \( n \) vertices, we show that \( \text{exp}(D) \leq 3n^2 + 2n – 2 \). For an asymmetric two-colored digraph \( D \) which contains a primitive two-colored cycle of length \( s \leq n \), we show its exponent is at most \( \frac{s^2 – 1}{2} + (s + 1)(n – s) \). We characterize such two-colored digraphs whose exponents equal \( \frac{s^2 – 1}{2} + (s + 1)(n – s) \) and show that the largest exponent of an asymmetric two-colored digraph lies in the interval \( \left[\frac{n^2 – 1}{2}, 3n^2 + 2n – 2\right] \) when \( n \) is odd, or \( \left[\frac{n^2}{2}, 3n^2 + 2n – 2\right] \) otherwise.

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;