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.

Stephan Foldes 1, Erkko Lehtonen2
1InsTITUTE OF MATHEMATICS, TAMPERE UNIVERSITY oF TECHNOLOGY, P.O. Box 553, FI-33101 TAMPERE, FINLAND
2InstTiTUTE oF MaTHEMATiICs, TAMPERE UNIVERSITY OF TECHNOLOGY, P.O. Box 553, FI-33101 TAMPERE, FINLAND
Abstract:

Let the columns of a \(p \times q\) matrix \(M\) over any ring be partitioned into \(n\) blocks, \(M = [M_1, \ldots, M_n]\). If no \(p \times p\) submatrix of \(M\) with columns from distinct blocks \(M_{i}\) is invertible, then there is an invertible \(p \times p\) matrix \(Q\) and a positive integer \(m \leq p\) such that \([QM_1, \ldots, QM_n]\) is in reduced echelon form and in all but at most \(m – 1\) blocks \(QM_i\) the last \(m\) entries of each column are either all zero or they include a non-zero non-unit.

Jeng-Jong Lin1
1Ling Tung University, Taichung 40852, Taiwan
Abstract:

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) \(G\) with vertex set \(V(G)\) is called a quasi-tree graph (respectively, quasi-forest graph), if there exists a vertex \(x \in V(G)\) such that \(G – x\) is a tree (respectively, forest). In this paper, we determine the largest numbers of maximal independent sets among all quasi-tree graphs and quasi-forest graphs. We also characterize those extremal graphs achieving these values.

Yongqiang Zhao1, Gerard J.Chang2,3,4
1Department of Mathematics Shijiazhuang College Shijiazhuang 050035, P.R. China
2Department of Mathematics National Taiwan University Taipei 10617, Taiwan
3Taida Institute for Mathematical Sciences National Taiwan University Taipei 10617, Taiwan
4National Center for Theoretical Sciences Taipei Office, Taiwan
Abstract:

In \(2004\), Fischermann et al. \([2]\) generalized bound polysemy to competition polysemy by using digraphs instead of posets. They provided a characterization of competition polysemic pairs and a characterization of the connected graphs \(G\) for which there exists a tree \(T\) such that \((G,T)\) is competition polysemic. In this paper, we continue to study the competition polysemy and characterize the connected graphs \(G\) for which there exists a triangle-free unicyclic graph \(G’\) such that \((G,G’)\) is competition polysemic. Furthermore,we generalize competition polysemy to \(m\)-competition polysemy and
prove a characterization of \(m\)-competition polysemic pairs.

Giovanni Lo Faro1, Antoinette Tripodi1
1Department of Mathematics University of Messina Contrada Papardo, 31 – 98166, Sant’Agata Messina, Italy
Abstract:

A diagonally switchable \(\lambda\)-fold \(4\)-cycle system of order \(n\), briefly DS4CS\((n, \lambda)\), is a \(\lambda\)-fold \(4\)-cycle system in which by replacing each \(4\)-cycle \((a,b,c,d)\) covering pairs \(ab, bc, cd, da\) by either of the \(4\)-cycles \((a,c,b,d)\) or \((a,d,c,b)\) another \(\lambda\)-fold \(4\)-cycle system is obtained. In \([3]\) Adams, Bryant, Grannell, and Griggs proved that a DS4CS\((n, 1)\) exists if and only if \(n \equiv 1 \pmod{8}\), \(n \geq 17\) with the possible exception of \(n = 17\). In this paper we prove that for \(\lambda \geq 2\) the necessary conditions for the existence of a \(A\)-fold \(4\)-cycle system of order \(7\) are also sufficient for the existence of a DS4CS\((n, \lambda)\) except for \((n, \lambda) = (5, 2)\).

Emrah Kilic1, Dursun Tasci2
1TOBB Economics AND TECHNOLOGY UNIVERSITY MATHEMATICS DEPARTMENT 06560 ANKARA TURKEY
2DEPARTMENT OF MATHEMATICS, Gazi UNIVERSITY 06500 ANKARA TURKEY
Abstract:

In this paper, we consider the relationships between the sums of the generalized order-\(k\) Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.

Abstract:

The ATSP polytope can be expressed by an asymmetric polynomial-size linear program.

Reza Ahangar1, Sarjinder Singh1, Rongdong Wang1
1Department of Mathematics, Texas A & M University-Kingsville, MSC 172, 700 University BLVD, Kingsville, Texas 78363-8202
Abstract:

A model that represents the rate of changes of the population with limited environmental resources can be described by,

\[
\frac{dp}{dt} = p\left(a – {bp}\right) + g(t,p) = p(t_0)= p_0
\]

where \( a \) measures the growth rate in the absence of the restriction force \( b \) and \( \frac{a}{b} \) is called the carrying capacity of the environment. The random perturbation \( g(t,P) \) is generated by random change in the environment. The behavior of the solution of this model for continuous and discrete case when \( g(t,P)=w(t) \) is density independent with a constant random factor \( w \) in a short time interval \([t, t + \delta t)\) will be studied. The stability and the behavior of the equilibrium point will also be investigated. A computational approach to the solution using Excel spreadsheet and Maple will be presented.

Futaba Okamoto1, Ping Zhang2
1Mathematics Department University of Wisconsin – La Crosse La Crosse, WI 54601
2Department of Mathematics Western Michigan University Kalamazoo, MI 49008
Abstract:

For a set \( S \) of two or more vertices in a nontrivial connected graph \( G \) of order \( n \), a collection \(\{T_1, T_2, \ldots, T_\ell\}\) of trees in \( G \) is said to be an internally disjoint set of trees connecting \( S \) if these trees are pairwise edge-disjoint and \( V(T_i) \cap V(T_j) = S \) for every pair \( i, j \) of distinct integers with \( 1 \leq i, j \leq \ell \). For an integer \( k \) with \( 2 \leq k \leq n \), the tree \( k \)-connectivity \( \kappa_k(G) \) of \( G \) is the greatest positive integer \( \ell \) for which \( G \) contains at least \( \ell \) internally disjoint trees connecting \( S \) for every set \( S \) of \( k \) vertices of \( G \). It is shown for every two integers \( k \) and \( r \) with \( 3 \leq k \leq 2r \) that
\[
\kappa_k(K_{r,r}) = r – \left\lceil \frac{k-1}{4} \right\rceil.
\]

Margaret A. Francel1, Spencer P. Hurd1
1Department of Mathematics and Computer Science The Citadel, Charleston, SC, 29409
Abstract:

This paper investigates the existence of monadic balanced ternary designs (BTDs). A monadic BTD is a BTD where each size \( K \) block contains one element that appears doubly and \( K-2 \) elements that appear singly. The authors show that the conditions

  1. \( \rho_1 = 2\rho_2 \),
  2. \( \Lambda(V-1) = 10\rho_2 \),
  3. \( \Lambda \neq 3 \),

are sufficient for the existence of monadic BTDs \( (V; B; \rho_1, \rho_2, R; 4; \Lambda) \). The authors also give necessary and sufficient conditions for the existence of monadic BTDs where the block size is five and \( \Lambda \) is 3 or 6.

J. Louis Sewell1, Peter J. Slater2
1Mathematical Sciences Department,University of Alabama in Huntsville Huntsville, AL 35899
2Computer Science Department University Of Alabama In Huntsville Huntsville, Al 35899 USA
Abstract:

We consider the placement of detection devices at the vertices of a graph \( G \), where a detection device at vertex \( v \) has three possible outputs: there is an intruder at \( v \); there is an intruder at one of the vertices in the open neighborhood \( N(v) \), the set of vertices adjacent to \( v \), but which vertex in \( N(v) \) cannot be determined; or there is no intruder in \( N[v] = N(v) \cup \{v\} \). We introduce the \( 1 \)-step locating-dominating problem of placing the minimum possible number of such detection devices in \( V(G) \) so that the presence of an intruder in \( V(G) \) can be detected, and the exact location of the intruder can be identified, either immediately or when the intruder has moved to an adjacent vertex. Some related problems are introduced.

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;