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

CREATORAryan Sanghi, Anubhav Dhar, Sudeshna Kolay
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-09585

Browse the full library · About the Tower of Babel