\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 Jakub Przyby{\l}o}
%
%
\medskip
\noindent
%
%
{\bf Irregularity Strength of Regular Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G$ be a simple graph with no isolated edges and at most one
isolated vertex. For a positive integer $w$, a $w$-weighting of
$G$ is a map $f:E(G)\rightarrow \{1,2,\ldots,w\}$. An irregularity
strength of $G$, $s(G)$, is the smallest $w$ such that there is a
$w$-weighting of $G$ for which $\sum_{e:u\in
e}f(e)\neq\sum_{e:v\in e}f(e)$ for all pairs of different vertices
$u,v\in V(G)$. A conjecture by Faudree and Lehel says that there
is a constant $c$ such that $s(G)\le{n\over d}+c$ for each
$d$-regular graph $G$, $d\ge 2$. We show that $s(G)<
16{n\over d}+6$. Consequently, we improve the results by Frieze,
Gould, Karo\'nski and Pfender (in some cases by a $\log n$ factor)
in this area, as well as the recent result by Cuckler and
Lazebnik.



\bye

.
