A Note on Repeated Degrees of Line Graphs - Kogan, Shimon (The Electronic Journal of Combinatorics, 2021)
Let rep(G) be the maximum multiplicity of a vertex degree in graph G. It was proven in Caro and West [E-JC, 2009] that if G is an n-vertex line graph, then rep(G) 14 n^1/3. In this note we prove that for infinitely many n there is a n-vertex line graph G such that rep(G) (2n)^1/3, thus showing that the bound above is asymptotically tight. Previously it was only known that for infinitely many n there is a n-vertex line graph G such that rep(G) 4n/3 (Caro and West [E-JC, 2009]). Finally we prove that if G is a n-vertex line graph, then rep(G) ((12-o(1))n)^1/3.