第２５卷 第ｌ期 Ｖｏ１．２５ Ｎｏ．１ 新乡学院学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｘｉｎｘｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） ２００８年３月 Ｍａｒ．２００８ 关于点赋权图的赋权控制数的一个上界 沈 健 ，孙玉芹 （１．同济大学数学系，上海２０００９２；２．上海电力学院数理系，上海２０００９０） 摘 要：点赋权图 一（ ，Ｅ，ｗ）是指对简单图Ｇ的顶点集作一个赋权函数 ：Ｖ—Ｒ 。在图Ｇ所有的控制集Ｄ Ｖ（Ｇ）（Ｖ（Ｇ）＼Ｄ中的任意顶点口都与Ｄ中的点关联）中最小的权和Ｗ（Ｄ）称为图Ｇ ．的赋权控制数，记作 （ ）。证明了对基数为Ｎ，平均权为ｗ的图Ｇ ，其赋权控制数‰（ ）≤ 关键词：赋权图；控制数；赋权控制数 中图分类号：Ｏ１５７．５ 文献标志码：Ａ 文章编号：１６７４—３３２６（２００８）０１—０００１—０２ 。 Ｔｈｅ Ｕｐｐｅｒ Ｂｏｕｎｄ ｏｆ Ｗｅｉｇｈｔｅｄ Ｄｏｍｉｎａｔｉｏｎ Ｎｕｍｂｅｒ ｏｆ Ｗｅｉｇｈｔｅｄ Ｇｒａｐｈ ＳＨＥＮ Ｊｉａｎ 。ＳＵＮ Ｙｕ－ｑｉｎ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００９２，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｐｈｙｃｉｓ ｏｆ Ｓｈａｎｇｈａｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ，Ｓｈａｎｇｈａｉ ２０００９０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｗｅｉｇｈｔｅｄ ｇｒａｐｈ Ｇ 一（Ｖ，Ｅ，ｗ）ｉｓ ａ ｇｒａｐｈ Ｇ ｔｏｇｅｔｈｅｒ ｗｉｔｈ ａ ｐｏｓｉｔｉｖｅ ｗｅｉｇｈｔ＿ｆｕｎｃｔｉｏｎ ｏｎ ｉｔｓ ｖｅｒｔｅｘ ｓｅｔ ：、，一Ｒ ．Ｔｈｅ ｗｅｉｇｈｔｅｄ ｄｏｍｉｎａｔｉｏｎ ｎｕｍｂｅｒ （Ｇ ）ｏｆ Ｇ ｉｓ ｔｈｅ ｍｉｎｉｍｕｍ ｗｅｉｇｈｔ ｗ（Ｄ）ｏｆ ａ ｓｅｔ Ｄ （Ｇ）ｓｕｃｈ ｔｈａｔ ｅｖｅｒｙ ｖｅｒｔｅｘ口ＥＶ（Ｄ）＼Ｄ ｈａｓ ａ ｎｅｉｇｈｂ。ｒｉｎ Ｄ．Ｔｈｉｓ ｐａｐｅｒ ｓｈ。ｗｓ ｔｈａｔ （ ）≤ ｇｒａｐｈ ｏｆ ｏｒｄｅｒ Ｎ ａｎｄ ａｖｅｒａｇｅ ｗｅｉｇｈｔ Ｗ． ｆ０ｒ ａ ｗｅｉｇｈｔｅｄ Ｋｅｙ ｗｏｒｄｓ：ｗｅｉｇｈｔｅｄ ｇｒａｐｈ；ｄｏｍｉｎａｔｉｏｎ ｎｕｍｂｅｒ；ｗｅｉｇｈｔｅｄ ｄｏｍｉｎａｔｉｏｎ ｎｕｍｂｅｒ ０ 引言 任意的顶点 都与Ｄ中的点关联。图Ｇ最小的控 制集基数称为控制数，记作），（Ｇ）。 点赋权图Ｇ 一（ ，Ｅ，ｗ）是指对简单图Ｇ的每 个顶点分配一个非负实数，这个实数称为相应顶点 图的控制数是图论中具有重要意义的图的参 数，有着广泛的应用背景。本文所讨论的图均指无 孤立点的有限简单图。首先，引人一些定义和记号。 设Ｇ一（ ，Ｅ）是简单图， （Ｇ）、Ｅ（Ｇ）分别表示图Ｇ 的顶点集和边集。对于任意顶点７３∈ （Ｇ），定义顶 点７Ｊ的开邻域Ｎ。［ ］一｛Ｕ∈ （Ｇ）：ｕｖＥＥ（Ｇ）｝，简 的权。换言之，Ｇｗ是对图Ｇ的顶点集作一个赋权 函数ｗ： —Ｒ 。对Ｄ （Ｇ）或者子图Ｈ，它们相 记为Ｎ（ ），顶点的闭邻ＮＧ［ ］一Ｎ （ ）Ｕ｛ ），简记 为ＮＥｖ］，顶点 在图Ｇ中的度，记作ｄ（ ）一ｆ Ｎ （ ）Ｊ，用 （Ｇ）表示图Ｇ的最小度，对Ｄ Ｖ，Ｇ［Ｄ］ 表示Ｄ在图Ｇ中的导出子图。Ｄ的开邻域Ｎｏ（Ｄ） 一应的权分别为 （Ｄ）一∑ ∈。Ｗ（ ）或者ｗ（Ｖ（Ｈ））。 在图Ｇ所有的控制集中最小的权和称为图Ｇ 的赋 权控制数，记作）， （Ｇ ．），即 （Ｇ ）一ｍｉｎ｛ｗ（Ｄ）： Ｄ是图Ｇ的控制集｝。如对图Ｇ的任意顶点都赋权 Ｕ 。Ｎ（ ），简记为Ｎ（Ｄ）。Ｄ的闭邻域Ｎ。［Ｄ］ 一ｕ 。Ｎ［ ］，简记为Ｎ［Ｄ］。如果Ｎ［Ｄ］＝＝＝Ｖ则称 为１，则显然 （Ｇ）一 （Ｇ），此时的赋权控制数是平 凡的。 Ｄ为图Ｇ的控制数，等价地说，对于 （Ｇ）＼Ｄ中的 收稿日期：２００８－０１—０５ 作者简介：沈健（１９８１一），男，江苏苏州人，同济大学数学系博士，主要从事组合数学及图论方面的研究工作。 对于图的控制集的研究有很多具体的形式，如 “Ｉｎｄｅｐｅｎｄｅｎｔ控制集”、“Ｅｆｆｉｃｉｅｎｔ控制集”、“Ｒｅ— ｓｔｒｉｃｔｅｄ控制集”、“Ｐｏｗｅｒ控制集”、“Ｔｏｔａｌ控制集”、 “Ｓｉｇｎｅｄ控制集”、“Ｃｏｎｎｅｃｔｅｄ控制集”、“Ｗｅａｋｌｙ 中，于是 Ｅ（１ ｙ ．Ｉ）一∑ （１一户）１Ｉ（１一户）一 ∑叫 （１～户） ≤Ｎｗ（１一ｐ）抖 。 因此，随机控制集ＸＵｙ的带权期望 Ｅ（Ｉ Ｘ ｌ＋１ｙ ．Ｉ）≤Ｎ 十Ｎ （１一 ） 十‘一 ｃｏｎｎｅｃｔｅｄ控制集”以及“Ｅｄｇｅ控制集”等。对一个 给定的图，找出它的某种具体控制集常常是困难的， 因此确定其界便成为十分有意义的工作，天才的数 学家Ｎ．Ａｌｏｎｌ１ 采用概率方法给出了图的基数充分 大时控制数的一个上界。定理的证明应用了随机方 Ｎ ［ｐ＋（１－－ｐ） ］。 由 （１一 ）抖 ≤ｅｘｐ［～ （ 十１）］一 法，它是一个广泛应用于众多学科的方法。文中涉 及随机图论的一些记号参见Ｂｏｌｌｏｂｄｓｌ＿２］。 定理１【３ 设图的顶点数为Ｎ，其最小度 ≥ １，则 （Ｇ）≤Ｎ 。 对于一般的赋权图Ｇ ，文献［４～７］等研究了一 些具体形式的赋权控制数，但就一般形式的赋权控 制 （ ）数尚未见相关的报道，本文将补上这一空 缺，给出一个类似上述定理的赋权控制数的上界。 １定理及证明 为叙述方便，以下设赋权图Ｇ 的顶点集为（１， ２，…，Ｎ｝，顶点ｉ对应的权为Ｗ ，平均权 １ Ｎ 训一 ∑Ｗ 。 Ｊ ｆ＝１ 定理２ 设图Ｇ 的顶点基数为Ｎ，平均权为 ，最小度为 ≥１，则其赋权控制数 （Ｇ ）≤ 。 ０ １ １ 证明 设 一 ，在赋权图Ｇ 中，以概 ０ Ｉ １ 率Ｐ随机地、独立地选取顶点 ，选取出来的顶点随 机地放进随机集Ｘ中。另设顶点子集ｙ— ＼（ＸＵ Ｎ（Ｘ））。易见，ＸＵｙ是图Ｇ 的一个随机的控制 集，下面考虑它的带权期望。首先， Ｅ（Ｉ Ｘ １）一∑叫 Ｐ＝Ｎ户 。 其次，ｙ中的点既不含在Ｘ中，也不含在Ｎ（Ｘ） ・ ２ ・ ｅｘｐ［一ｌｎ（ 十１）］一 ， 可知 Ｅ（ＬＸ Ｉ＋ｌｖ ≤Ｎ 。 又因为赋权图Ｇ 的赋权控制数不超过Ｅ（１ Ｘ ｌ＋ｊ ｝），定理得证。 参考文献： ［１］Ａｌｏｎ Ｎ，Ｓｐｅｎｃｅｒ Ｊ Ｈ．Ｔｈｅ Ｐｒｏｂａｂｉｌｉｓｔｉｅ Ｍｅｔｈｏｄ［Ｍ］． Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅｙ－Ｉｎｔｅｒｓｃｉｅｎｃｅ，１９９２． ［２］Ｂ．Ｂｏｌｌｏｂｄｓ，Ｒａｎｄｏｍ Ｇｒａｐｈｓ（２ｎｄ ｅｄ．）［Ｍ］，Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，Ｌｏｎｄｏｎ－Ｎｅｗ Ｙｏｒｋ，２００ １． ［３３ Ａｌｏｎ Ｎ．Ｔｈｅ ｍａｘｉｍａｌ ｎｕｍｂｅｒ ｏｆ Ｈａｍｉｌｔｏｎｉａｎ ｐａｔｈｓ ｉｎ ｔｏｕｒｎａｍｅｎｔｓ［Ｊ］．Ｃｏｍｂｉｎａｔｏｒｉｃ，１９９０，（１Ｏ）：３１９－３２４． ［４］Ｇｅｒａｒｄ Ｊ．Ｃｈａｎｇ，Ｔｈｅ ｗｅｉｇｈｔｅｄ ｉｎｄｅｐｅｎｄｅｎｔ ｄｏｍｉｎａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｓ ＮＰ—ｃｏｍｐｌｅｔｅ ｆｏｒ ｃｈｏｒｄａｌ ｇｒａｐｈｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，２００４，（１４３）：３５１—３５２． ［５］Ｐｅｔｅｒ Ｄａｎｋｅｌｍａｎｎ，Ｄｉｅｔｅｒ Ｒａｕｔｅｎｂａｃｈ，Ｌｕｔｚ Ｖｏｌｋｍａｎｎ， Ｗｅｉｇｈｔｅｄ ｄｏｍｉｎａｔｉｏｎ ｉｎ ｔｒｉａｎｇｌｅ－ｆｒｅｅ ｇｒａｐｈｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ｍａｔｈｅｍａｔｉｃｓ，２００２（２５０）：２３３—２３９． ［６］Ｃｈｉｎ Ｌｕｎｇ Ｌｕ，Ｃｈｕａｎ Ｙｉ Ｔａｎｇ，Ｗｅｉｇｈｔｅｄ ｅｆｆｉｃｉｅｎｔ ｄｏｍｉ— ｎａｔｉｏｎ ｐｒｏｂｌｅｍ ｏｎ ｓｏｍｅ ｐｅｒｆｅｃｔ ｇｒａｐｈｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ａｐ— ｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，２００２（１７７）：１６３—１８２． ［７］Ｃｈａｉｎ—Ｃｈｉｎ Ｙｅｎ，Ｒ．Ｃ．Ｔ．Ｌｅｅ，Ｔｈｅ ｗｅｉｇｈｔｅｄ ｐｅｒｆｅｃｔ ｄｏｍｉｎａｔｉｏｎ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ｖａｒｉａｎｔｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，１９９６（６６）：１４７—１６Ｏ． 【责任编辑邢怀民】