A note on repeated degrees of line graphs (Q2048571): Difference between revisions

Summary: Let \(\text{rep}(G)\) be the maximum multiplicity of a vertex degree in graph \(G\). It was proven in [\textit{Y. Caro} and \textit{D. B. West}, Electron. J. Comb. 16, No. 1, Research Paper R7, 14 p. (2009; Zbl 1178.05029)] that if \(G\) is an \(n\)-vertex line graph, then \(\text{rep}(G) \geqslant \frac{1}{4} n^{1/3} \). In this note we prove that for infinitely many \(n\) there is an \(n\)-vertex line graph \(G\) such that \(\text{rep}(G) \leqslant \left(2n\right)^{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 \(\text{rep}(G) \leqslant \sqrt{4n/3} \) [loc. cit.]. Finally we prove that if \(G\) is an \(n\)-vertex line graph, then \(\text{rep}(G) \geqslant \left(\left(\frac{1}{2}-o(1)\right)n\right)^{1/3} \).