1. Perfect Hermitian rank-metric codesUsman Mushrraf, 2026, izvirni znanstveni članek Opis: This study investigates Hermitian rank-metric codes, a special class of rank-metric codes, focusing on perfect codes and on the analysis of their packing properties. Firstly, we establish bounds on the size of spheres in the space of Hermitian matrices and, as a consequence, we show that non-trivial perfect codes do not exist in the Hermitian case. We conclude the paper by examining their packing density.
Ključne besede: Hermitian matrix, packing density, perfect code
Objavljeno v RUP: 16.09.2026; Ogledov: 286; Prenosov: 5
 Celotno besedilo (396,90 KB) |
2. Linear bounds on treewidth in terms of excluded planar minorsJ. Pascal Gollin, Kevin Hendrey, Sang-il Oum, Bruce Reed, 2025, izvirni znanstveni članek Opis: One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for $f(H)$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth $\Omega(k\log k)$ which does not contain $k$ vertex-disjoint cycles, from which it follows that $f(H) = \Omega(k\log k)$. In particular, if $f(H)$ is linear in $\lvert V(H) \rvert$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most $\lvert V(H) \rvert$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to $f(H)$≤$n$+O(√$n$) when $r$=2. In particular this bound is linear when $r$=O(√$n$/logn). We present a linear bound for $f(H)$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for $f(H)$ when $H$ is the wheel graph or the 4×4 grid, obtaining a bound of 160 for the latter.
Ključne besede: graph minor, treewidth, cycle packing
Objavljeno v RUP: 05.01.2026; Ogledov: 1418; Prenosov: 3
Celotno besedilo (613,98 KB)
Gradivo ima več datotek! Več... |
3. A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groupsJ. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, Youngho Yoo, 2025, izvirni znanstveni članek Opis: In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs (l, z) of integers where such a duality holds for the family of cycles of length l modulo z. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.
Ključne besede: Erdős-Pósa property, cycle packing, group-labelled graph
Objavljeno v RUP: 17.11.2025; Ogledov: 1237; Prenosov: 13
Celotno besedilo (1,17 MB)
Gradivo ima več datotek! Več... |
4. k-Domination ivariants on Kneser graphsBoštjan Brešar, Tanja Dravec, María Gracia Cornet, Michael A. Henning, 2025, izvirni znanstveni članek Opis: In this follow-up to work of M.G. Cornet and P. Torres from 2023, where the k-tuple domination number and the 2-packing number in Kneser graphs K(n, r) were studied, we are concerned with two variations, the k-domination number, γ_k(K(n, r)), and the k-tuple total domination number,
γ_{t × k}(K(n, r)), of K(n, r). For both invariants we prove monotonicity results by showing that γ_k(K(n, r)) ≥ γ_k(K(n + 1, r)) holds for any n ≥ 2(k + r), and γ_{t × k}(K(n, r)) ≥
γ_{t × k}(K(n + 1, r)) holds for any n ≥ 2r + 1. We prove that γ_k(K(n, r)) = γ_{t × k}(K(n, r)) = k + r when n ≥ r(k + r), and that in this case every γ_(k)-set and γ_(t × k)-set is a clique, while γ_k(r(k + r) − 1, r) = γ_{t × k}(r(k + r) − 1, r) = k + r + 1, for any k ≥ 2. Concerning the 2-packing number, ρ₂(K(n, r)), of K(n, r), we prove the exact values of ρ₂(K(3r − 3, r)) when r ≥ 10, and give sufficient conditions for ρ₂(K(n, r)) to be equal to some small values by imposing bounds on r with respect to n. We also prove a version of monotonicity for the 2-packing number of Kneser graphs.
Ključne besede: Kneser graphs, k-domination, k-tuple total domination, 2-packing
Objavljeno v RUP: 22.10.2025; Ogledov: 815; Prenosov: 10
Celotno besedilo (375,34 KB) |
5. On optimal λ-separable packings in the planeKároly Bezdek, Zsolt Lángi, 2025, izvirni znanstveni članek Opis: Let P be a packing of circular disks of radius ρ > 0 in the Euclidean, spherical, or hyperbolic plane. Let 0 ≤ λ ≤ ρ. We say that P is a λ-separable packing of circular disks of radius ρ if the family P′ of disks concentric to the disks of P having radius λ form a totally separable packing, i.e., any two disks of P′ can be separated by a line which is disjoint from the interior of every disk of F′. This notion bridges packings of circular disks of radius ρ (with λ = 0) and totally separable packings of circular disks of radius ρ (with λ = ρ). In this note we extend several theorems on the density, tightness, and contact numbers of disk packings and totally separable disk packings to λ-separable packings of circular disks of radius ρ in the Euclidean, spherical, and hyperbolic plane. In particular, our upper bounds (resp., lower bounds) for the density (resp., tightness) of λ-separable packings of unit disks in the Euclidean plane are sharp for all 0 ≤ λ ≤ 1 with the extremal values achieved by λ-separable lattice packings of unit disks. On the other hand, the bounds of similar results in the spherical and hyperbolic planes are not sharp for all 0 ≤ λ ≤ ρ although they do not seem to be far from the relevant optimal bounds either. The proofs use local analytic and elementary geometry and are based on the so-called refined Molnár decomposition, which is obtained from the underlying Delaunay decomposition and as such might be of independent interest.
Ključne besede: Euclidean, spherical and hyperbolic plane, λ-separable packing, density, tightness, contact number, refined Molnar decomposition
Objavljeno v RUP: 21.10.2025; Ogledov: 1042; Prenosov: 12
Celotno besedilo (776,44 KB) |
6. |
