CS Paper Radar

On Multi-label radio Labelings of Graphs

Olivier Togni

cs.DM math.CO ·submitted 2026-10-19 06:18 UTC · v2
theory

Abstract

We propose and study a multi-labeling generalization of the $k$-radio labeling problem of graphs: given a graph $G$ and integers $k$ and $m$, assign to each vertex of $G$ a set of $m$ integer labels such that distinct labels assigned to a vertex differ by at least $k+1$, and the labels of any two distinct vertices $x$ and $y$ pairwise differ by at least $k+1-d(x,y)$, with $d(x,y)$ being the distance between vertices $x$ and $y$. We prove general bounds on the minimum span of such a labeling and more refined results for the case $k=1$. For paths and cycles, we derive sharp bounds on the minimum span when $k$ is small. We finally propose a conjecture for the minimum span on the path and for an almost-tight bound on the cycle.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal radio labelings for the Cartesian product of a path and the Heawood graph

cs.DM math.CO ·2026-11-10 ·Payal Vasoya, Miral Doshi, Devsi Bantva
theoryhot direction similarity 0.74
Abstract · 24 pages, 1 figures

For a simple graph $G$, let $d(u,v)$ denote the distance between two vertices $u$ and $v$ in $G$, and let $diam(G)$ denote the diameter of $G$. A radio labeling of $G$ is a mapping $f : V(G) \rightarrow \mathbb{N} \cup \{0\}$ such that $|f(u)-f(v)|\geq diam(G) + 1 - d(u,v)$ holds for every pair of distinct vertices $u, v \in G$. The span of $f$ is the difference between the largest and smallest integers assigned by $f$, and the radio number $rn(G)$ is the minimum span taking over all radio labelings of $G$. Let $P_n$ denote the path on $n$ vertices and let $H$ denote the Heawood graph (see Figure-1). In this paper we determine the radio number for the Cartesian product of a path and the Heawood graph, and characterize all optimal radio labelings of $P_n \Box H$. Moreover, we show that the radio number of $P_n \Box H$ exceed the lower bound given for $rn(G)$ in [6], where $G$ is any graph, and that this gap is arbitrarily large.

0.28

Hardness Results for Approximate Distance Labeling in Sparse Graphs

cs.DS ·2026-11-02 ·Tsvi Kopelowitz, Ariel Korin, Liam Roditty
top venuetheory similarity 0.72
Abstract · To appear in SODA 2027

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

0.38

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.67
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

cs.DS ·2026-09-08 ·Yaowei Long, Seth Pettie, Thatchaphol Saranurak
similarity 0.67
Abstract · 11 pages

For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = Ω(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.

0.37

Triameter, distance packings, and vertex connectivity

cs.DM math.CO ·2026-11-12 ·Artem Hak, Sergiy Kozerenko
theory similarity 0.66
Abstract · Preliminary version, any comments are welcome

We study upper bounds for the triameter of a connected graph in terms of distance packings and vertex connectivity. For any positive integer $k$, we bound the triameter of a graph by a linear function of its $k$-packing number and show that this bound is tight for all values of the parameters. As a corollary, we confirm the conjecture of Das and Abdioğlu on the upper bound for the triameter in terms of the order and the minimum degree of a graph. We also find the maximum triameter among graphs with given order and vertex connectivity, and describe the extremal graphs. Our main tool is a projection of a graph onto a spider or a unicyclic graph which preserves the distances between three prescribed vertices.

0.23

The Cayley Completion of a Graph

cs.DM cs.DSmath.CO ·2026-08-31 ·Rigobert Fokam Souop, Laurent Bitjoka
theory similarity 0.62
Abstract

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completion number $γ^{+}$ (additions only) and the Cayley edit distance $γ_{\triangle}$ (both), each normalized by $m$. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is $n+m-2k$ when it realizes a longest path with $k$ edges; the optimal cost is $m-n+2pp(G)$, bounded in polynomial time by the matching number. We prove that irregularity alone forces $γ^{+}(G)\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\geΔ$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $γ^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $γ^{+}$, while $γ_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $γ_{\triangle}(K_{1,q})\to 2$, not the $3/2$ suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on $89.4\%$ and the two invariants separate strictly on $84.7\%$, though both rates vary sharply with order: attainment $100\%,100\%,84.8\%,89.7\%$ and separation $0\%,61.9\%,73.2\%,87.7\%$ for $n=4,5,6,7$, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.

0.49

Small classes have linear neighbourhood complexity

cs.DM math.CO ·2026-11-11 ·John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
theory similarity 0.62
Abstract · 31 pages, 6 figures

A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.

0.22

Maximal Linear Arrangement is NP complete on Bipartite Graphs

cs.DM math.CO ·2026-10-08 ·Aparna Das, Jonathan Needleman
theory similarity 0.62
Abstract · 11 pages

The linear arrangement of a simple graph $G = (V,E)$ is a bijective labeling $π$ of the vertices of $G$ to the set $\{1, \ldots, n\}$. The maximum linear arrangement ($\texttt{maxLA}$) problem is to determine whether $G$ has a labeling such that the sum of labels across $G$'s edges, $\sum_{uv \in E} |π(u) - π(v)|$, is at least a given value $k$. Minimum linear arrangement ($\texttt{minLA}$) is defined analogously. Both $\texttt{maxLA}$ and $\texttt{minLA}$ are known to be NP complete for general graphs. $\texttt{minLA}$ has shown to be NP complete for bipartite graphs by Evans and Shiloah in 1975. It has been an open problem whether the same holds for $\texttt{maxLA}$. In this paper we prove that $\texttt{maxLA}$ is NP complete for bipartite graphs.

0.33