若干Double图的点可区别边染色

由引理 １ 知
况 予 以证 明 。
（ Ｓ ） ， 证 定 理 为 真 ， 需 给 出 Ｄ（ ） 要 仅
Ｄ（ 的一个 （ （ ）一ＶＤ Ｃ法 ， ．） ｓ Ｊ ．） Ｄｓ Ｅ 以下 分 两 种情
情 况 １当 ｔ＝１时 ， 然 Ｄ（ ／ ， 显 Ｓ ）＝Ｃ ， 由文 献
定义 ２对简单图 Ｇ，， ６ △分别表示 Ｇ的最小 度
２ 主 要 结 果 ｌ 相 关 定 义 及 引 理
定 义 １１２ 无 孤立 边 且 至 多 有 一 个 孤 立点 的 ＿－］ 对 简 单 图 Ｇ Ｖ Ｅ） 一个 一正 常边 染 色 法 ¨ 厂 若满 （， 的 ’ 足 Ｖｕ ∈Ｖ Ｇ ， ， （ ） 且 ≠口 有 Ｃ Ⅱ ， （ ）≠Ｃ（ 。则 称 ， ） 为 Ｇ的一个 后一点可 区别 边染 色 法 ， 简记 作 Ｇ的 尼一 Ｖ Ｅ Ｄ Ｃ法 。而 ｔ：ｒｉ Ｉ 的 一Ｖ Ｅ ｄ ａｎ｛ Ｇ Ｄ Ｃ法 ｝ 为 称 Ｇ的点 可 区别边 色 数 。其 中 Ｃ（ ）．｛（ ） ｕ Ｗ ， 删 ｌ， ， － ｌ ｄ Ｖ∈Ｅ （ ） 称 为点 在 厂下 的色 集 ， （，在色 全集 合 Ｃ＝ Ｇ ｝ Ｃ／ ／ ）
和 大度 ， 示 Ｇ中度 为 ｉ ｎ表 的点 数 ， 表 示 ｍ 个 不 Ｃ 同元 素 中任取 ｎ个 元 素 的组 合 数 ， 称 Ｉ（ 则 Ｊ Ｇ）＝ｍａ ． ｘ ｛ ｉ Ｃ ≥／，≤ ≤Ａ｝ 为 Ｇ的组合 度 。 ａ ｒｎ… ： ７ ６ ， ｉ ｝ 猜 想 （ Ｄ Ｃ ¨ 对 Ｉ （ ）ｌ Ｖ Ｅ Ｃ） ｃ ≥３的 连 通 图 Ｇ，
了星 、 和 轮 的 Ｄ ｕｌ 的点 可 区别 边 色 数 。 文 中 扇 ｏｂｅ图 未加 述 及 的术语 、 号 可参 见 ¨ 记 。
引理 ２对 简单 图 Ｇ的 Ｄ ｕ ｌ ， △（ Ｇ） ｏ ｂｅ图 有 Ｄ（ ）
＝
２ （ ） 且 ／ 与 其对 应点 口 的度相 同 。 ＡＣ ， ３ ，
｛ ， … ， ｝ 的补 集 记 为 Ｃ ＼ ｕ 。 １２， Ｊ 中 ｉ ｝ Ｃ Ｃ（ ）
…
定理 １对 ／＋１阶星 Ｓ ／ ， 的 Ｄ ｕ ｌ Ｄ（ ， ｏ ｂｅ图 Ｓ ） 有
｛ ２ １
证 明 ： １＋１阶 星 Ｓ 记 ７ ， 为 ：（ Ｖ ｓ ）＝｛ Ｉ＝ ， ， Ｏ １ ｉ
引理 １ Ｉ 对 Ｉ （ ２ Ｇ）≥３Ｉ 连 通 图 Ｃ 有 Ｖ 的 ，
（ ） ／（ ） Ｇ １ｚ Ｇ 。 ＞
些 联 图 Ｐ 、 Ｖ 、 ＶＣ Ｖ Ｓ Ｃ 和 Ｃ 的点 ＶＩ ｓ
可区别边色数 。文献 ［ ］ ８ 定义 了图的 Ｄ ｕｌ ｏｂ ｅ图， 文 献［ １ ］ ９— １ 分别得 到了一些倍 图 的均匀 全色数、 邻 点 可 区别 均 匀 全色 数 和 均 匀 邻 强 边 色 数 ， 文 给 出 本
有 （ ） Ｇ （ ≤ Ｇ Ｇ） （ ）＋１ 。
［］ １ 中结论可知 （ ＝ ， Ｃ ） ４ 此时结论成立 。 情 况 ２当 ｎ ２时 ， Ｃ＝｛ ， … ， ＋１ ， ， ｔ ＞ 设 １２， ２ ｝令
题 就 是确 定 其各 种染 色法 的色数 。为解 决 网络权 的 分配 等 问题 ，ｕ ＇、 忠 辅 等 人 先 后 提 出 了图 的 点 Ｂ ｎｓ张 ｉ 可 区别 边染 色 和 邻 强 边 染 色 概 念 Ｊ得 到 了若 干 ，
２ Ｅ（ Ｇ） ） Ｄ（ ）＝Ｅ（ ）ｕＥ（ Ｇ Ｇ ）ｕ ｛ｉ ∈Ｖ Ｕ ｌ
（． １ 西北 民族 大学 现代教育技术学 院 ， 甘肃 兰州 ７０３ ； 西北 民族大学 数学 与计算机科学学 院 ， ３００２ ． 甘肃 兰州 ７０３ ） ３００
摘 要 ： 一个 正常的边染 色满足不 同点 的点所 关联边色集合不 同， 对 称为点可 区别边 染色 （ Ｄ Ｃຫໍສະໝຸດ ， Ｖ Ｅ ） 其所用最 少染 色
（ ） ｔ ∈ Ｇ ） 且 ／ｕ Ｅ （ ）｝ Ｇ ， （ ， ／ ｉ Ｇ 。 ， ＇ ｉ 则 称 Ｄ（ ） Ｇ的 Ｄ ｕ ｌ 。 Ｇ为 ｏ ｂｅ图
结果 ， 并提出了有关猜想 。文献 ［ ７ 分别得到 了 ５— ］
一
由定 义 １定 义 ２和定义 ３可知 有下 述 引理 １及 、 引理 ２成 立 。
数称为点可 区别边 色数。就此用构 造法研究 了一些 Ｄ ｕ ｌ ｏｂｅ图的点 可区别边染色 ， 得到 了星 、 扇和轮的 Ｄ ｕｌ ｏ ｂｅ图的点 可区别边色数 ， 验证 了它们满 足点可区别边染 色猜想（ Ｄ Ｃ 。 Ｖ Ｅ Ｃ） 关键词 ： ｏ ｂ Ｄ ｕｌ ； ｅ图 点可区别边染色 ； 点可 区别边 色数
，
ｎ ；（ ｝Ｅ Ｓ ）＝｛０‘ｉ ， ， ， ｝ Ｕ Ｉ ＝１２ … ｔ 。若 ／＝１ ／ ， ／ ， ，
（ ｜） Ｄ（ ）＝ｍｉ ｚＣ ＞４｝＝ 若 ｎ ， Ｄ（ ） ｓ ｎ｛Ｉ １ ４； ≥２ （ Ｊｎ ｓ
＝ ａ｛ ｉ｛ｌ；Ｉ２ ， ｉｌＩ； ２ ｝ ＝ ｎ＋１ ｍ ｘ ｒｎ ｆｃ ｝ｒｎ １ ｎ ｝ ２ ａ ＞ ａ ＞ ２Ｃ 。
中图分类 号 ： １７ ５ ０ ５ ．
具 有 重 要 实 际 意 义 和 理 论 意 义 的 图 的染 色 问
题 ， 图论研 究 的主 要 内容之 一 ， 是 图的染 色 的基本 问
为 ／ ， 应 的顶 点 为 。若 满足 ｚ Ｇ相
１ ｌ Ｄ（ ） （ ） （ ； ）， Ｇ ）＝ Ｇ ｕ Ｇ ） （
第２ ８卷
第 ９期
甘肃科 技
Ｇａ ｓ ｃ ｅ ｃ ｎ ｃ ｎ ｎ ｕ Ｓ ｉｎ ｅ ａ ｄ Ｔｅ ｈ ｏ
Ｉ ２ Ⅳ０ ９ ｆ ８ ． ．
Ｍａ ． ２ ２ ｙ ０１
２１ ０ ２年 ５月
若 干 Ｄ ｕ ｌ 的点 可 区别 边 染 色 ｏ ｂｅ图
马 强 ， 刚 ， 马 田富鹏