Repetition number of graphs
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.
- A note on repeated degrees of line graphs
- Equating maximum degrees in graphs without short cycles
- Induced subgraphs with many repeated degrees
- Regular independent sets
- Large induced subgraphs with three repeated degrees
- Repetitions in graphs and sequences
- Forcing k-repetitions in degree sequences
- scientific article; zbMATH DE number 1062586 (Why is no real title available?)
- Fair domination in graphs
- Large induced subgraphs with \(k\) vertices of almost maximum degree
- Equating two maximum degrees
- scientific article; zbMATH DE number 2187677 (Why is no real title available?)
- Bounding the First Zagreb Index of a Tree in Term of Its Repetition Number
- Equating three degrees of graphs
- Large induced subgraphs with equated maximum degree
This page was built for publication: Repetition number of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010910)
