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.

Abdullah Altin1, Bayram Cekim2, Esra Erkus-Duman2
1Ankara University, Faculty of Science, Department of Mathematics, Tandogan TR-06100, Ankara, Turkey
2Gazi University, Faculty of Sciences and Arts, Department of Mathematics, Teknikokullar TR-06500, Ankara, Turkey.
Abstract:

The Jacobi matrix polynomials and their orthogonality only for commutative matrices was first studied by Defez \(et. al\).
[Jacobi matrix differential equation, polynomial solutions and their properties. Comput. Math. Appl. \(48 (2004), 789-803]\). It is known that orthogonal matrix polynomials comprise an emerging field of study, with important results in both theory and applications continuing to appear in the literature. The main object of this paper is to derive various families of linear, multilateral and multilinear generating functions for the Jacobi matrix polynomials and the Gegenbauer matrix polynomials. Recurrence relations of Jacobi matrix polynomials are obtained. Some special cases of the results presented in this study are also indicated.

Guihai Yu1,2, Linua Feng3, Qingwen Wang2, Aleksandar Ilié4
1School of Mathematics, Shandong Institute of Business and Technology, Yantai, Shandong, P.R. China, 264005.
2Department of Mathematics, Shanghai University, Shanghai, 200444.
3Department of Mathematics, Central South University, Changsha, Hunan, 410083.
4Faculty of Sciences and Mathematics, University of NiS, Serbia, 18000.
Abstract:

The positive index of inertia of a signed graph \(\Gamma\), denoted by \(,(\Gamma)\), is the number of positive eigenvalues of the adjacency matrix \(A(\Gamma)\) including multiplicities. In this paper we investigate the minimal positive index of inertia of
signed unicyclic graphs of order \(n\) with fixed girth and characterize the extremal graphs with the minimal positive index. Finally, we characterize the signed unicyclic graphs with the positive indices \(1\) and \(2\).

Hailong Hou1, Rui Gu1
1 School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang, 471003, P.R. China
Abstract:

In this paper, we explicitly explore the endomorphism monoid of the circulant complete graph \(K(n, 4)\). We demonstrate that \(Aut(K(n,4)) \cong D_n\), the dihedral group of degree \(n\). Furthermore, we show that \(K(n,4)\cong D_n\) is unretractive for \(n = 4m , 4m +2\) (\(m \geq 2\)), and that \(End(K(n,4)) = qEnd(K(n,4))\) and \(sEnd(K(n,4)) = Aut(K(n,4))\) when \(n = 4m, 4m + 2\) (\(m \geq 2\)). Additionally, we prove that \(End(K(4m,4))\) is regular and \(End(K(4m + 2,4))\) is completely regular. We also solve some enumerative problems concerning \(End(K(n,4))\) are solved.

Stefan O.Tohaneanu1
1DEPARTMENT OF MATHEMATICAL SCIENCES, UNIVERSITY OF CINCINNATI, CINCINNATI, OH 45221-0025,
Abstract:

In this note we find a necessary and sufficient condition for the supersolvability of an essential, central arrangement of rank \(3\) (\(i.e\), line arrangement in the projective plane). We present an algorithmic way to decide if such an arrangement is supersoivable or not that does not require an ordering of the lines as the Bjémer-Ziegler’s and Peeva’s criteria require. The method uses the duality between points and lines in the projective plane in the context of coding theory.

Xiaoxia Wu1, Lianzhu Zhang2, Hawei Dong3, Chengfu Qin4
1School of Mathematics and Statistics, Minnan Normal University, Fujian 363000, China
2School of Mathematical Sciences, Xiamen University, Fujian 861005, China,
3Department of Mathematics, Minjiang University, Fujian 850108, China
4 Department of Mathematics, Guangxi Teachers Education University, Guangzi 530001, China
Abstract:

This paper deals with the Abelian sandpile model on the generalized trees with certain given boundary condition. Using a combinatorial method, we obtain the exact expressions for all single-site probabilities and some two-site joint probabilities. Also, we prove that the sites near the boundary have a different height probability from those away from it in bulk for the Bethe lattice with the boundary condition, which is the same as those results found by Grassberger and Manna [Some more sandpiles,” J.Phys.(France)\(51,1077-1098(1990)\)] and proved by Haiyan chen and Fuji Zhang [“Height probabilities in the Abelian sandpile on the generalized finite Bethe lattice” J. Math. Phys. \(54, 083503 (2013))\).

Edray Herber Goins1, Talitha M.Washington2
1DEPARTMENT OF MATHEMATICS, PURDUE UNIVERSITY, 150 NORTH UNIVERSITY STREET, WEST LAFAYETTE, IN 47907
2DEPARTMENT OF MATHEMATICS, 1800 LINCOLN AVENUE, UNIVERSITY OF EVANSVILLE, EVANSVILLE, IN 47722
Abstract:

Let \(S\) be a subset of the positive integers and \(M\) be a positive integer. Inspired by Tony Colledge’s work, Mohammad K. Azarian considered the number of ways to climb a staircase with \(n\) stairs using “step-sizes” \(s \in S\) with multiplicities at most \(M\). In this exposition, we find a solution via generating functions, i.e., an expression counting the number of partitions \(n = \sum_{s \in S} m_ss\), satisfying \(0 \leq m_s \leq M\). We then use this result to answer a series of questions posed by Azarian, establishing a link with ten sequences listed in the On-Line Encyclopedia of Integer Sequences (OEIS). We conclude by posing open questions that seek to count the number of compositions of \(n\).

Premysl Holub1
1Department of Mathematics, University of West Bohemia, and Institute for Theo- retical Computer Science (ITI), Charles University, Univerzitni 22, 306 14 Pilsen, Czech Republic
Abstract:

Hamiltonian index of a graph \(G\) is the smallest positive integer \(k\), for which the \(k\)-th iterated line graph \(L^k(G)\) is hamiltonian. Bedrossian characterized all pairs of forbidden induced subgraphs that imply hamiltonicity in \(2\)-connected graphs. In this paper, some upper bounds on the hamiltonian index of a \(2\)-connected graph in terms of forbidden not necessarily induced subgraphs are presented.

Mehdi Eliasi1, Bijan Taeri2
1Department of Mathematics, Faculty of Khansar, University of Isfahan Isfahan 81746-73441, Iran
2Department of Mathematical Sciences, Isfahan University of Technology Isfahan 84156-83111, Iran
Abstract:

The Szeged polynomial of a connected graph \(G\) is defined as \(S_z(G,x) = \sum_{e \in E(G)} x^{n_{u(e) n_v(e)}} \), where \(n_u(e)\) is the number of vertices of \(G\) lying closer to \(u\) than to \(v\), and \(n_v(e)\) is the number of vertices of \(G\) lying closer to \(v\) than to \(u\). Ashrafi et al. (On Szeged polynomial of a graph, Bull. Iran. Math. Soc. \(33 (2007) 37-46)\) proved that if \(|V(G)|\) is even, then \(\deg(S_z(G,x)) \leq \frac{1}{4}{|V(G)^{2}} |\). In this paper, we investigate the structure of graphs with an even number of vertices for which equality holds, and also examine equality for the sum of graphs.

Shude Long1, Junliang Cai2
1Department of Mathematics, Chongqing University of Arts and Sciences, Chongqing 402160, P.R.China
2School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P.R.China
Abstract:

In this paper we investigate the number of rooted loopless unicursal planar maps and present some formulae for such maps with up to three parameters: the number of edges and the valencies of the two odd vertices.

Muhammad Imran1, A.Q. Baig2, M.K. Shafiq2, Ioan Tomecu3
1Center for Advanced Mathematics and Physics (CAMP), National University of Science and Technology (NUST) Sector H-12, Islamabad, Pakistan
2 Department of Mathematics, GC University Faisalabad, Pakistan
3Faculty of Mathematics and Computer Science, University of Bucharest Str. Academiei, 14, 010014 Bucharest, Romania
Abstract:

In this paper, we investigate the metric dimension of generalized Petersen graphs \(P(n,3)\), providing a partial answer to an open problem posed in [8]: whether \(P(n,m)\) for \(n \geq 7\) and \(3 \leq m \leq \left\lfloor \frac{n-1}{2} \right\rfloor\) constitutes a family of graphs with constant metric dimension. Specifically, we prove that the metric dimension of \(P(n,3)\) equals \(3\) for \(n \equiv 1 \pmod{6}\), \(n \geq 25\), and equals \(4\) for \(n \equiv 0 \pmod{6}\), \(n \geq 24\). For remaining cases, four judiciously chosen vertices suffice to resolve all vertices of \(P(n,3)\), implying \(\dim(P(n,3)) \leq 4\), except when \(n \equiv 2 \pmod{6}\), in which case \(\dim(P(n,3)) \leq 5\).

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;