论文标题
邻居总和通过本地约束区分边缘加权
Neighbour sum distinguishing edge-weightings with local constraints
论文作者
论文摘要
$ g $的$ k $ - edge加权是映射$ω：e（g）\ longrightArrow \ {1，\ ldots，k \} $。 $ g $的边缘重视自然会诱导$σ_Ω：v（g）\ longrightArrow \ mathbb {n} $由$σ_Ω（v）= \ sum_ {u \ in n_g（v）中的$ v \ in v in n_g（vu）$ v \ in v（g）$。边缘权威的$ω$是邻居总和，以区分它是否产生适当的顶点$σ_Ω$，\ emph {i.e。}，$σ_Ω（u）\ neqσ_Ω（v）$ $ g $的每个边缘$ uv $。不是单色。如果没有组件同构为$ k_2 $，则图表很好。我们证明，每个具有最高度最高度的漂亮图形均可承认一个邻居总和区分$（δ（g）+2）$ - 边缘加权，因此所有至少2个学位的顶点至少有两个不同权重的边缘。此外，我们证明每个漂亮的图都承认一个邻居总和区分$ 7 $ - edgedGeighting，因此所有学位的顶点至少约6个都有至少两个不同权重的边缘。最后，我们表明，不错的两分图承认一个邻居总和区分$ 6 $ - edgedgeighting，使所有学位的顶点至少〜2都出现，至少有两个不同权重的边缘。
A $k$-edge-weighting of $G$ is a mapping $ω:E(G)\longrightarrow \{1,\ldots,k\}$. The edge-weighting of $G$ naturally induces a vertex-colouring $σ_ω:V(G)\longrightarrow \mathbb{N}$ given by$σ_ω(v)=\sum_{u\in N_G(v)}ω(vu)$ for every $v\in V(G)$. The edge-weighting $ω$ is neighbour sum distinguishing if it yields a proper vertex-colouring $σ_ω$, \emph{i.e.}, $σ_ω(u)\neq σ_ω(v)$ for every edge $uv$ of $G$.We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(Δ(G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.
