Irregularity Strength of Regular Graphs
Irregularity Strength of Regular Graphs
复制标题
DOI：
10.37236/806
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
J. Przybylo
中科院分区：
文献类型：
--
作者：
J. Przybylo
设$G $是一个没有孤立边且至多有一个孤立点的简单图。对于一个正整数$w $，$G $的一个$w $加权是一个映射$f：E（G）\rightarrow\{1，2，\ldots，w\}$。$G $的不规则性强度$s（G）$是最小的$w $使得存在$G $的$w $-加权使得$\sum_{e：u\in e} f（e）\neq\sum_{e：v\in e} f（e）$对于V（G）$中的所有不同顶点对$u，v\。Faudree和莱赫尔的一个猜想说，存在一个常数c使得对每个d $-正则图G $，$d\ge2 $，$s（G）\le {n\over d}+ c $。我们证明了$s（G）
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)