\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Yair Caro and Douglas B. West}
%
%
\medskip
\noindent
%
%
{\bf Repetition Number of Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.

\bye