1661. The cut method on hypergraphs for the Wiener indexSandi Klavžar, Gašper Domen Romih, 2023, original scientific article Abstract: The cut method has been proved to be extremely useful in chemical graph theory. In this paper the cut method is extended to hypergraphs. More precisely, the method is developed for the Wiener index of $k$-uniform partial cube-hypergraphs. The method is applied to cube-hypergraphs and hypertrees. Extensions of the method to hypergraphs arising in chemistry which are not necessary $k$-uniform and/or not necessary linear are also developed. Keywords: hypergraphs, Wiener index, cut method, partial cube-hypergraphs, hypertrees, phenylene, Clar structures Published in DiRROS: 15.03.2024; Views: 365; Downloads: 139
Full text (318,45 KB) This document has many files! More... |
1662. Faster distance-based representative skyline and k-center along pareto front in the planeSergio Cabello, 2023, original scientific article Abstract: We consider the problem of computing the distance-based representative skyline in the plane, a problem introduced by Tao, Ding, Lin and Pei and independently considered by Dupin, Nielsen and Talbi in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$, the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n \log h)$ time, where $h$ is the number of points in the skyline of $P$. We also show that the decision problem can be solved in $O(n \log k)$ time and the optimization problem can be solved in $O(n \log k + n \log\log n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$. Keywords: geometric optimization, skyline, pareto front, clustering, k-center Published in DiRROS: 15.03.2024; Views: 329; Downloads: 153
Full text (2,13 MB) This document has many files! More... |
1663. Proper holomorphic maps in Euclidean spaces avoiding unbounded convex setsBarbara Drinovec-Drnovšek, Franc Forstnerič, 2023, original scientific article Abstract: We show that if $E$ is a closed convex set in $\mathbb C^n$, $n>1$ contained in a closed halfspace $H$ such that ▫$E\cap bH$▫ is nonempty and bounded, then the concave domain $\Omega=\mathbb C^n\setminus E$ contains images of proper holomorphicmaps $f : X \to \mathbb C^n$ from any Stein manifold $X$ of dimension $< n$, with approximation of a givenmap on closed compact subsets of $X$. If in addition $2 {\rm dim} X+1 \le n$ then $f$ can be chosen an embedding, and if $2 {\rm dim} X = n$, then it can be chosen an immersion. Under a stronger condition on $E$, we also obtain the interpolation property for such maps on closed complex subvarieties. Keywords: Stein manifolds, holomorphic embeddings, Oka manifold, minimal surfaces, convexity Published in DiRROS: 15.03.2024; Views: 264; Downloads: 130
Full text (441,34 KB) This document has many files! More... |
1664. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, original scientific article Abstract: Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine. Keywords: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number Published in DiRROS: 14.03.2024; Views: 340; Downloads: 140
Full text (453,39 KB) This document has many files! More... |
1665. |
1666. The liberation set in the inverse eigenvalue problem of a graphJephian C.-H. Lin, Polona Oblak, Helena Šmigoc, 2023, original scientific article Abstract: The inverse eigenvalue problem of a graph $G$ is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of $G$. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al. in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form $M=A \oplus B$ and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices. Keywords: symmetric matrix, inverse eigenvalue problem, strong spectral property, Matrix Liberation Lemma, zero forcing Published in DiRROS: 14.03.2024; Views: 277; Downloads: 144
Full text (626,24 KB) This document has many files! More... |
1667. |
1668. |
1669. On the Schrödinger-Poisson system with $(p,q)$-LaplacianYueqiang Song, Yuanyuan Huo, Dušan Repovš, 2023, original scientific article Abstract: We study a class of Schrödinger-Poisson systems with $(p,q)$-Laplacian. Using fixed point theory, we obtain a new existence result for nontrivial solutions. The main novelty of the paper is the combination of a double phase operator and the nonlocal term. Our results generalize some known results. Keywords: double phase operator, Schrödinger-Poisson systems, (p, q)–Laplacian, fixed point theory Published in DiRROS: 14.03.2024; Views: 303; Downloads: 167
Full text (686,98 KB) This document has many files! More... |
1670. Recent developments on Oka manifoldsFranc Forstnerič, 2023, review article Abstract: In this paper we present the main developments in Oka theory since the publication of my book "Stein Manifolds and Holomorphic Mappings (The Homotopy Principle in Complex Analysis)", 2nd ed., Springer, 2017. We also give several new results, examples and constructions of Oka domains in Euclidean and projective spaces. Furthermore, we show that for $n > 1$ the fibre $\mathbb C^n$ in a Stein family can degenerate to a non-Oka fibre, thereby answering a question of Takeo Ohsawa. Several open problems are discussed. Keywords: Oka manifold, Oka map, Stein manifold, elliptic manifold, algebraically subelliptic manifold, Calabi–Yau manifold, density property Published in DiRROS: 14.03.2024; Views: 664; Downloads: 557
Full text (1014,41 KB) This document has many files! More... |