Repetition number of graphs (Q1010910): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 22:15, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Repetition number of graphs |
scientific article |
Statements
Repetition number of graphs (English)
0 references
7 April 2009
0 references
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.
0 references
multiplicitx of vertex degree
0 references
average degree
0 references
minimum degree
0 references
trees
0 references
maximal outerplanar graphs
0 references
planar triangulations
0 references
claw free graphs
0 references
line grpahs
0 references