Repetition number of graphs

Yair Caro ; Douglas B. West

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

Every $n$-vertex graph has two vertices with the same degree (if $n\ge2$). In general, let rep$(G)$ be the maximum multiplicity of a vertex degree in $G$. An easy counting argument yields rep$(G)\ge 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)\ge{1\over4}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.

Détail

DOI : 10.37236/96

Classification : 05C07, 05C35, 05C76
Mots-clés : multiplicitx of vertex degree, average degree, minimum degree, trees, maximal outerplanar graphs, planar triangulations, claw free graphs, line grpahs