Repetition number of graphs (Q1010910): Difference between revisions

Summary: Every \(n\)-vertex graph has two vertices with the same degree (if \(n\geq 2\)). In general, let rep\((G)\) be the maximum multiplicity of a vertex degree in \(G\). An easy counting argument yields rep\((G)\geq n/(2d-2s+1)\), where \(d\) is the average degree and \(s\) is the minimum degree of \(G\). Equality can hold when \(2d\) is an integer, and the bound is approximately sharp in general, even when \(G\) is restricted to be a tree, maximal outerplanar graph, planar triangulation, or claw-free graph. Among large claw-free graphs, repetition number 2 is achievable, but if \(G\) is an \(n\)-vertex line graph, then rep\((G)\geq\frac{1}{4}n^{1/3}\). Among line graphs of trees, the minimum repetition number is \(\Theta(n^{1/2})\). For line graphs of maximal outerplanar graphs, trees with perfect matchings, or triangulations with 2-factors, the lower bound is linear.