1851. |
1852. |
1853. |
1854. |
1855. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, original scientific article Abstract: The $2$-packing number $\rho_2(G)$ of a graph $G$ is the cardinality of a largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is the cardinality of a largest open packing of $G$, where an open packing (resp. $2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$. For hypercubes, the lower bounds $\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$ and $\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$ are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that $Q_9$ is the smallest hypercube which is not perfect injectively colorable. It is also proved that $\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$, where $H$ is an arbitrary graph with no isolated vertices. Keywords: 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number Published in DiRROS: 19.02.2024; Views: 501; Downloads: 172
Full text (231,57 KB) This document has many files! More... |
1856. Oka domains in Euclidean spacesFranc Forstnerič, Erlend Fornæss Wold, 2024, original scientific article Abstract: In this paper, we find surprisingly small Oka domains in Euclidean spaces $\mathbb C^n$ of dimension $n>1$ at the very limit of what is possible. Under a mild geometric assumption on a closed unbounded convex set $E$ in $\mathbb C^n$, we show that $\mathbb C^n\setminus E$ is an Oka domain. In particular, there are Oka domains only slightly bigger than a halfspace, the latter being neither Oka nor hyperbolic. This gives smooth families of real hypersurfaces $\Sigma_t \subset \mathbb C^n$ for $t \in \mathbb R$ dividing $\mathbb C^n$ in an unbounded hyperbolic domain and an Oka domain such that at $t=0$, $\Sigma_0$ is a hyperplane and the character of the two sides gets reversed. More generally, we show that if $E$ is a closed set in $\mathbb C^n$ for $n>1$ whose projective closure $\overline E \subset \mathbb{CP}^n$ avoids a hyperplane $\Lambda \subset \mathbb{CP}^n$ and is polynomially convex in $\mathbb{CP}^n\setminus \Lambda\cong\mathbb C^n$, then $\mathbb C^n\setminus E$ is an Oka domain. Keywords: Oka manifold, hyperbolic manifolds, density property, projectively convex sets Published in DiRROS: 19.02.2024; Views: 519; Downloads: 156
Full text (278,96 KB) This document has many files! More... |
1857. On orders of automorphisms of vertex-transitive graphsPrimož Potočnik, Micael Toledo, Gabriel Verret, 2024, original scientific article Abstract: In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with $n$ vertices and of valence $d$, $d\le 4$, is at most $c_d n$ where $c_3=1$ and $c_4 = 9$. Whether such a constant $c_d$ exists for valencies larger than $4$ remains an unanswered question. Further, we prove that every automorphism $g$ of a finite connected $3$-valent vertex-transitive graph $\Gamma$, $\Gamma \not\cong K_{3,3}$, has a regular orbit, that is, an orbit of $\langle g \rangle$ of length equal to the order of $g$. Moreover, we prove that in this case either $\Gamma$ belongs to a well understood family of exceptional graphs or at least $5/12$ of the vertices of $\Gamma$ belong to a regular orbit of $g$. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms $C$ of a connected $3$-valent vertex-transitive graph $\Gamma$ in terms of the number of vertices of $\Gamma$ and the length of a longest orbit of $C$. Keywords: graphs, automorphism groups, vertex-transitive, regular orbit, cubic, tetravalent Published in DiRROS: 19.02.2024; Views: 415; Downloads: 171
Full text (573,20 KB) This document has many files! More... |
1858. Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar, Eva Zmazek, 2024, original scientific article Abstract: A set of vertices $X$ of a graph $G$ is a strong edge geodetic set if to any pair of vertices from $X$ we can assign one (or zero) shortest path between them such that every edge of $G$ is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of $G$ is the strong edge geodetic number ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature. Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs Published in DiRROS: 19.02.2024; Views: 355; Downloads: 146
Full text (430,75 KB) This document has many files! More... |
1859. Complete nonsingular holomorphic foliations on Stein manifoldsAntonio Alarcón, Franc Forstnerič, 2024, original scientific article Abstract: Let $X$ be a Stein manifold of complex dimension $n \ge 1$ endowed with a Riemannian metric ${\mathfrak g}$. We show that for every integer $k$ with $\left[\frac{n}{2}\right] \le k \le n-1$ there is a nonsingular holomorphic foliation of dimension $k$ on $X$ all of whose leaves are topologically closed and ${\mathfrak g}$-complete. The same is true if $1\le k \left[\frac{n}{2}\right]$ provided that there is a complex vector bundle epimorphism $TX\to X \times \mathbb{C}^{n-k}$. We also show that if $\mathcal{F}$ is a proper holomorphic foliation on $\mathbb{C}^n$ $(n > 1)$ then for any Riemannian metric ${\mathfrak g}$ on $\mathbb{C}^n$ there is a holomorphic automorphism $\Phi$ of $\mathbb{C}^n$ such that the image foliation $\Phi_*\mathcal{F}$ is ${\mathfrak g}$-complete. The analogous result is obtained on every Stein manifold with Varolin's density property. Keywords: Stein manifolds, complete holomorphic foliations, density property Published in DiRROS: 19.02.2024; Views: 375; Downloads: 157
Full text (433,06 KB) This document has many files! More... |
1860. Lower (total) mutual-visibility number in graphsBoštjan Brešar, Ismael G. Yero, 2024, original scientific article Abstract: Given a graph $G$, a set $X$ of vertices in $G$ satisfying that between every two vertices in $X$ (respectively, in $G$) there is a shortest path whose internal vertices are not in $X$ is a mutual-visibility (respectively, total mutual-visibility) set in $G$. The cardinality of a largest (total) mutual-visibility set in $G$ is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in $G$, and denote them by $\mu^{-}(G)$ and $\mu_t^{-}(G)$, respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph $G$, we prove that both differences $\mu^{-}(G)-\mu_t^{-}(G)$ and $\mu_t^{-}(G)-\mu^{-}(G)$ can be arbitrarily large. We characterize graphs $G$ with some small values of $\mu^{-}(G)$ and $\mu_t^{-}(G)$, and prove a useful tool called the Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with the Bollobás-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to $\mu_t^{-}(G)$. Keywords: mutual-visibility set, mutual-visibility number, total mutual-visibility set, computational complexity Published in DiRROS: 19.02.2024; Views: 353; Downloads: 153
Full text (567,18 KB) This document has many files! More... |