On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs
Aryan Sanghi, Anubhav Dhar, Sudeshna Kolay · 2026
Read On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs by Aryan Sanghi, Anubhav Dhar, Sudeshna Kolay (2026) 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-2602-09585.txt.
Description
Aryan Sanghi and two co-authors study iterated line graphs. Each edge of a graph becomes a vertex, linked when edges share an endpoint, and the operation repeats. Their 2026 paper asks two questions for a graph on n vertices. For which iteration counts does the iterated line graph admit an Euler path? How does its maximum degree grow? Since iterated line graphs can dwarf the original, both answers need efficient methods.
For Euler paths, the largest iteration count admitting one grows at most like vertices times edges. An algorithm lists all such counts in polynomial time. For degree growth, paths, cycles, and claws are easy. All other connected graphs, called prolific, follow a formula. Beyond some iteration, degree equals a graph constant times a power of two plus two. The smallest such constants are three, four, five and a half, six, and seven, with full characterizations for the first four.
Catalog record
| CREATOR | Aryan Sanghi, Anubhav Dhar, Sudeshna Kolay |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-09585