Separating path systems for cubic graphs and for complete bipartite graphs
Cristina G. Fernandes, Carlos Hoppen, George Kontogeorgiou, Guilherme Oliveira Mota, Danni Peng · 2025
Read Separating path systems for cubic graphs and for complete bipartite graphs by Cristina G. Fernandes, Carlos Hoppen, George Kontogeorgiou, Guilherme Oliveira Mota, Danni Peng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12781.txt.
Introduction
Cristina Fernandes and four co-authors study separating path systems, collections of paths that can tell every pair of edges in a graph apart. For any two edges, some path must use one and not the other. The smallest size of such a system is the graph's strong separation number. The authors prove that every 2-degenerate graph on n vertices, a class where every part has a low-degree vertex, has separation number at most n.
From that result they derive bounds for subcubic graphs, planar graphs, and planar bipartite graphs. For complete bipartite graphs they prove lower bounds in two size regimes and give a construction that meets the bound in one of them. The paper appeared in final form in Discrete Mathematics. Such systems matter where paths must distinguish connections.
Catalog record
| CREATOR | Cristina G. Fernandes, Carlos Hoppen, George Kontogeorgiou, Guilherme Oliveira Mota, Danni Peng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-12781
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Separating path systems for cubic graphs and for complete bipartite graphs Thanks: We would like to thank Maya Stein for inviting us to the 2 n d 2^{nd} Graph Theory in the Andes Workshop, where this work was undertaken. This study was partly supported by a joint project FAPESP and ANID (2019/13364-7) and by CAPES (Finance Code 001). C.G. Fernandes was supported by CNPq (312511/2025-6, 404315/2023-2) and FAPESP (2023/03167-5). C. Hoppen was supported by CNPq (315132/2021-3 and 408180/2023-4). G. Kontogeorgiou was supported by ANID (Grant CMM Basal FB210005) and ANID-FONDECYT Postdoctorado Grant No. 3250479. G.O. Mota was supported by CNPq (315916/2023-0 and 406248/2021-4) and FAPESP (2023/03167-5 and 2024/13859-4). D. Peng was supported by CNPq (141537/2023-0). Cristina G. Fernandes, Carlos Hoppen, George Kontogeorgiou, Guilherme Oliveira Mota, Danni Peng Abstract . A strongly separating path system in a graph G G is a collection 𝒫 \mathcal{P} of paths in G G such that, for every two edges e e and f f of G G , there is a path in 𝒫 \mathcal{P} with e e but not f f , and vice-versa. The minimum size of such a system is the so called strong separation number of G G . We prove that the strong separation number of every 2 2 -degenerate graph on n n vertices is at most n n . Using this, we also provide upper bounds for the strong separation number of subcubic graphs, planar graphs, and planar bipartite graphs. On the other hand, we prove that the strong separation number of a complete bipartite graph K a , b K_{a,b} is at least b b if a < b / 2 a<b/2 and at least ( 6 ( b / 2 ) + 4 − 2 ) a (\sqrt{6(b/2)+4}-2)a if b / 2 ≤ a ≤ b b/2\leq a\leq b , and we provide a construction that attains the former bound. 1. Introduction Given a collection \mathcal{P} of paths in a graph G , we say that two edges e,f in G are separated by \mathcal{P} if there are two paths P_{e} and P_{f} in \mathcal{P} such that P_{e} contains e but avoids f , and P_{f} contains f but avoids e . We say that \mathcal{P} is a strongly separating path system of G if \mathcal{P} separates every pair of edges in G . The minimum size of a strongly separating path system of G is denoted by \mathrm{ssp}(G) . Balogh, Csaba, Martin, and Pluhár [ 1 ] conjectured that \mathrm{ssp}(G)=\mathrm{O}(n) for every n -vertex graph G , and succeeded in establishing an upper bound of \mathrm{O}(n\log n) on \mathrm{ssp}(G) . A substantial improvement to \mathrm{O}(n\log^{\ast}n) was made by Letzter [ 8 ] . Finally, Bonamy, Botler, Dross, Naia, and Skokan [ 2 ] proved an upper bound of 19n , settling the conjecture as true. The bound of 19n is not tight and it is possible that \mathrm{ssp}(G)\leq(1+o(1))\,n for every connected n -vertex graph G , 1 1 1 In [ 1 ] , the authors claim an example of a graph G with \mathrm{ssp}(G)\geq(2-\varepsilon)n , but their proof has a flaw that invalidates this statement: the length of a longest path in K_{\varepsilon n,(1-\varepsilon)n} is 2\varepsilon n and not \varepsilon n+1 . where the connectivity condition is necessary, as the graph consisting of n/4 disjoint copies of K_{4} requires 5n/4 paths to be strongly separated. Recently, the first and fourth authors together with Sanhueza-Matamala [ 4 ] proved that \mathrm{ssp}(K_{n})=(1+o(1))n and \mathrm{ssp}(K_{\frac{n}{2},\frac{n}{2}})=(\sqrt{5/2}-1+o(1))\,n , and in general obtained the asymptotic value of \mathrm{ssp}(G) for \alpha n -regular n -vertex graphs that are robustly connected . For complete graphs, this result was further improved by the third author and Stein [ 6 ] , who constructed a strongly separating path system for K_{n} with at most n+9 paths. In this work, we continue this line of research by establishing new bounds for 2-degenerate graphs (Section 2 ) and for complete bipartite graphs (Section 4 ). A graph G is 2 -degenerate if every subgraph of G contains a vertex of degree at most 2 . The class of 2-degenerate graphs includes, for instance, all outerplanar graphs, all series-parallel graphs, all strictly subcubic graphs, and all planar graphs of girth at least 6. Our first main result is the following. Theorem 1.1 . For every 2 -degenerate n -vertex graph G , we have \mathrm{ssp}(G)\leq n . Our proof is inductive and yields a separating path system \mathcal{P} with some very convenient properties. Namely, if every connected component of G contains at least three vertices, then \mathcal{P} is such that every edge of G is contained in exactly two of its paths, and every vertex of G is the endpoint of exactly two of its paths. In Section 3 , we apply Theorem 1.1 to obtain upper bounds for \mathrm{ssp}(G) when G is subcubic, planar, or planar bipartite. We also study separating path systems for unbalanced complete bipartite graphs K_{a,b} , a\leq b . If a<b/2 , we show that \mathrm{ssp}(K_{a,b})=b . For a\geq b/2 , we establish a lower bound of (\sqrt{6(b/a)+4}-2)a on \mathrm{ssp}(K_{a,b}) . This bound is tight at the extremes, that is, when a=b/2 and when a=b . In what follows, we refer to a path just by its sequence of vertices. That is, for a path with vertex set \{v_{1},\ldots,v_{\ell}\} where v_{i}v_{i+1} is an edge for every 1\leq i\leq\ell-1 , we write P=(v_{1},\dots,v_{\ell}) . 2. 2-Degenerate graphs In this section, we prove that \mathrm{ssp}(G)\leq n for every 2-degenerate n -vertex graph G . In fact, we prove a stronger statement which will be useful for our other results and gives an extra structural property for our strongly separating path systems for 2 -degenerate graphs. Theorem 2.1 . For every connected 2 -degenerate graph G on n\geq 3 vertices, there is a strongly separating path system for G with n paths and the following two properties: (i) every edge lies in exactly two paths; (ii) there are exactly two paths ending at each vertex of G . Before going into the proof, note that, if G_{1},\ldots,G_{k} are the connected components of a graph G , then \mathrm{ssp}(G)=\sum_{i=1}^{k}\mathrm{ssp}(G_{i}) . In particular, if \mathrm{ssp}(G_{i})\leq|V(G_{i})| for i=1,\ldots,k , then \mathrm{ssp}(G)\leq n . Moreover, a connected component that is a single edge can be separated by a single path. This explains why we restrict our attention to connected graphs of size at least 3 . Proof. The proof is by induction on n . If n=3 , then G is either a path of length 2 or a triangle. If G is path of length 2 , say (v_{1},v_{2},v_{3}) , the family \{(v_{1},v_{2},v_{3}),\,(v_{1},v_{2}),\,(v_{2},v_{3})\} , is a strongly separating path system for G satisfying (i) and (ii) . If G is a triangle with vertices \{v_{1},v_{2},v_{3}\} , then our strongly separating path system satisfying (i) and (ii) is \{(v_{1},v_{2},v_{3}),\,(v_{2},v_{3},v_{1}),\,(v_{3},v_{1},v_{2})\} . For the induction step, consider n\geq 4 , and assume that the result holds for any connected 2-degenerate graph with fewer than n vertices. Firstly, suppose that G has a vertex v of degree at most 2 for which G-v is connected. If v has degree 1, consider a separating path system \mathcal{P}^{\prime} for G-v