终稿《图论本科毕业论文--符号控制数》.doc

华东交通大学毕业论文 1 目 录 摘 要 2 ABSTRACT 3 第一章 引 言 4 第二章 图的符号边控制 6 2 1 星图符号边控制数 7 2 2 路径的符号边控制数 8 2 3 圈的符号边控制数 9 2 4 树的符号边控制数 11 2 5 正则图的符号边控制数 13 2 6 符号星控制数的界 16 第三章 结 论 18 第四章 谢 辞 19 参考文献 20 附 录 21 A 外文翻译 原文部分 21 B 外文翻译 译文部分 28 刘峰 关于图的边控制数 2 关于图的边控制数 摘 要 本文综述了近期关于图的边控制数的若干结果 例如星图 路径 圈 树 正则图 的符号边控制数的一些确切值或其界值 同时对其中的一些结果给出了另一种证明方法 在路径和圈的问题上 提出了结构单元的思想 从而有效地减少了讨论情况 在树的符 号边控制数的论证过程中 提出了把树拆分成若干星图 利用星图的结论进行论证得到 树的符号边控制数的下界 并且给出了等号成立的一种条件图 最后对一般图的符号星 控制数给出了一个新的下界 并且给出了详细的证明过程 关键词 符号边控制函数 符号星控制函数 符号边控制数 符号星控制数 结构单元 华东交通大学毕业论文 3 On edge domination numbers of graphs ABSTRACT This paper summarizes some results on edge domination numbers of graphs in the past periods such as some accurate values on edge domination numbers of the star graph path circuit tree and the regular graph or their boundary value Meanwhile it has provided another certificate method to some results In the tree and the circuit question the author has put forward the structural unit theory reduced the classification discuss circumstance effectively During the proof process on edge domination numbers of the tree the author put forward dismantling a tree to several star graphs and get the lower bound of the signed edge domination numbers tree get the conclusion by making use of the star graph s And the author gives an equality condition graph when the equal mark is tenable Finally give a new lower bound to the general graph of the signed star domination number and gives the detailed certificate process Keywords Signed edge domination function Signed star domination function Signed edge domination number Signed star domination number Structural unit 刘峰 关于图的边控制数 4 第一章 引 言 本文所指的图 均为无向简单且连通图 本文中未加说明的符号和术语均同于文献 1 设一图 其中分别是的点集和边集 当时 GV G E G V GE G和G vV G 且记集合则表示点 在中的邻域 同时集合 G NvvE G vv 邻接于 G NvvG 表示点 在中的闭邻域 为点 在中的度 为了方 GG NvNvv vG GG dvNv vG 便起见 有时将分别简记为若时 且记集 GGG Nv Nv dv N v N v d v euvE G 合则表示点在中的邻域 表示 G NeeE G ee 邻接于 G NeeG GG NeNee 边在中的闭邻域 表示边在中的度 很明显eG GG deNe eG 同理 将分别简记为若 2 GGG dedudv GGG Ne Ne de N e N e d e 则记集合表示点 在中的边邻域 简记 为了 vV G G EvuvE G uV G vG E v 帮助理解以上几个概念 我们用图 1 1 说明如下 华东交通大学毕业论文 5 图 1 1 是原图 G 表示 和 42356 N vv v v v 423456 N vv v v v v 43578 e e e E ve 表示 和 735689 N ee e e e e 7356789 N ee e e e e e 近几年来 图的控制理论研究的内容越来越广泛 各类控制概念相继产生 而且研 究成果不断丰富 同时也为图论研究提供了许多新思维和新方法 T W Haynes 等人的两 部专著 5 6 综述了近些年来图的控制理论研究方面的主要研究成果 这部分主要讨论的绝 大多数属于图的点控制 徐保根教授又在文 2 3 中分别引入了图的两种边控制概念即 符 号边控制和符号星控制 在文 7 中引入了另一种边控制概念即 图的符号圈控制 近期 徐教授还对边控制概念进行延拓 提出了局部符号控制概念 在这一系列的研究过程中 徐教授得出了较多的研究成果 大力地推动了图的控制理论的发展 定义 1 1 设是一个图 一个二值函数称作为符号边控制函 GV E 1 1 fE 数 如果对任意边都成立 SEDF signed edge domination function 1 eN e f e eE G 的符号边控制数定义为 G min s e E G Gf efGSEDF 是的 定义 1 2 设是一个图 一个二值函数称作为符号星控制 GV E 1 1 fE 函数 如果对任意顶点都成 SSDF signed star domination function 1 e E v f e vV G 立 的符号星控制数定义为 G min ss e E G Gf efGSSDF 是的 对于空图 有定义 n GK 0 sss GG 刘峰 关于图的边控制数 6 第二章 图的符号边控制 引理 2 1 Xu 3 对于任何两个点不相交的图 我们有 12 GG和 和 1212 sss GGGG 1212 ssssss GGGG 若讨论的是图不连通则可以使用此引理得到相应的结果 GV E 定义 2 1 设是一个图 表示图的顶点序列 称为 如果 GV E d GGG 图 也就是说均包含一个圈和两个端点在圈上的一条路 2 2 2 3 3 d G 图 图 2 1 图 定理 2 1 任意一个均包含一个偶圈 圈含有偶数条边 图 证明 不失一般性 假设是一个连通图 首先我们把图分成两个子图 GG 12 GG和 根据的定义 我们把度数为 3 的顶点进行标记为 而两个子 图vw和 3d vd w 图满足 1212 12 GGG GGvw vwvw GGGvw 表示点到的一条路 同时可以知道定点度数含有两种值 为此我们分以下两种情况讨论 G 我们假设中含有偶数个 2 根据路的长度也分为两种情 2 2 2 3 3 d G vw 华东交通大学毕业论文 7 况讨论 当为奇数 则为奇数 从而可知必定是一奇一vw 12 GGGvw 12 GG和 偶 由的定义知均为圈 故必定有一个是偶圈 结论成立 图 12 GG和 当为偶数 则为偶数 故取则也vw 12 GGGvw CG vw CGvw 为偶数 结论成立 我们假设中含有奇数个 2 根据路的长度也分为两种情 2 2 2 3 3 d G vw 况讨论 当为奇数 则为偶数 故取则也vw 12 GGGvw CG vw CGvw 为偶数 结论成立 当为偶数 则为奇数 从而可知必定是一奇一vw 12 GGGvw 12 GG和 偶 由的定义知均为圈 故必定有一个是偶圈 结论成立 图 12 GG和 综上所述 我们得知结论成立 2 1 星图符号边控制数 定理 2 2 设是一个星图 且 若为奇数则 若为 TV E E Tm m 1 s T m 偶数则 2 s T 证明 如图 2 2 是一个星图 很明显 有对 则 如果是的 eE T T NeE T fT 图 2 2 星图 刘峰 关于图的边控制数 8 则因为故分为两种情况 SEDF 1 T e E TeNe f ef e T NeE Tm 若为奇数 则令 则的取法为 其中任取条边标记为 记m21mk f1k 1 为且 取剩余的为 1 ETeE Gf e 1ETk 1 ETeE Gf e 知 故 ETk 1 s TEE 若为偶数 则令 则的取法为 其中任取条边标记为 记为m2mk f1k 1 且 取剩余的为 1 ETeE Gf e 1ETk 1 ETeE Gf e 知 故 1ETk 2 s TEE 综上所述 结论成立 2 2 路径的符号边控制数 定理 2 3 对任意一条路 那么它的符号边控制数由以下关系 2 m P m 1 2 0 mod3 3 1 2 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Pmm Pmm Pmm 证明 首先分析路的特性 在路中任选一条边 假设若对定义为 eE G SEDF 则两端的边必有 若对定义为 则两端 1f e 12 e e 12 1f ef e SEDF 1f e 的边必有两边的函数值之积为即 由此 我们可以构造一个结构 12 e e 1 12 1f ef e 单元如图 2 3 所示 使得 即此 31331 1 1 1 320 31 iii f ef ef eiim 且 结构只在中间出现不能够在两端出现 同时必定有两端的四条边满足 12 1 1 mm f ef ef ef e 结构单元 华东交通大学毕业论文 9 图 2 3 由以上定义的可知满足符号边控制函数的定义 接下来我们来讨论计算符号边SEDF 控制数 分三种情况讨论 则知有个结构单元剩余三条边不在结构单元中有定0 mod3 m 3 3 m 11 mm e ee 义知 31 1 1 1 32 33 sm m Pm 则知有个结构单元剩余四条边不在结构单元中有1 mod3 m 4 3 m 121 mmm e eee 定义知 41 14 2 2 33 sm m Pm 则知有个结构单元剩余两条端边不在结构单元中有定义2 mod3 m 2 3 m 1 m e e 知 21 12 1 1 33 sm m Pm 综上所述 本定理结论成立 2 3 圈的符号边控制数 定理 2 4 对任意一条路 那么它的符号边控制数由以下关系 m C 1 0 mod3 3 1 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Cmm Cmm Cmm 证明 同定理 2 3 首先分析圈的特性 我们同样通过构造如图 2 3 的结构单元来定 义符号边控制函数 如图 2 4 我们也分为三种情况进行讨论 刘峰 关于图的边控制数 10 图 2 4 则从开始三个一组划分 所有的边都在如图 2 3 的结构中 且0 mod3 m 1 e 均满足符号边控制函数的定义 故 1 3 sm Cm 则知除去终边外 从开始三个一组划分 所有的边都在如图 2 3 1 mod3 m m e 1 e 的结构中 且均满足符号边控制函数的定义 而 故 1 m f e 11 1 1 2 33 sm Cmm 则知除去两条边外 从开始三个一组划分 所有的边都在如2 mod3 m 1 mm ee 1 e 图 2 3 的结构中 且均满足符号边控制函数的定义 而 故 1 1 mm f ef e 11 2 2 1 1 33 s mm 综上所述 本定理结论成立 在以下的定理证明过程当中 首先需要对一些术语和数学符号进行声明一下 设是一个图 且 表示从图中通过删除边的 GV E uvE G G uv 1 GK uv 同时增加一条新的边 其中 很明显有 且uw 1 Kw V G uvV Gw 如图 2 5 所示 图表示原图 图表示 E G uvE G GV E G uv 华东交通大学毕业论文 11 图 2 5 设是一个图 它的为 则我们记为一个符号图 对于一个 GV E SEDFf G f 符号图 我们由定义 1 1 可知 G f s e E G Gf e 简单地说 给定一个符号图 一条边 若则在图上标记为 G f eE G 1f e 类似地 若则在图上标记为 我们记 1 1f e 1 1 1 EG feE Gf eEG feE Gf e 且 对于任意的符号图 它的两个生成子图和定义为 H g Hg Hg 同时我们称 V HgV HgV HE HgEH gE HgEH g 且 和分别为符号图的正负子图 一般地 对于任意一个顶点 Hg Hg H g uV H 称为顶点在符号图上的符号度数 若有 dH g uu H g 在不混淆的情况下我们可以把简记为 HgHg dH g ududu dH g u d u 2 4 树的符号边控制数 定理 2 5 对任意一棵树 则有其控制数 TV E 1 s T 证明 很明显任意一棵树都可以分解为若干星图的并 即有 星图之间的连 0 k i i TT 接边为 01 1 iiiiiii Ee eu ueE TuV Tik 且 依据上面所述 我们对下图进行分解T 刘峰 关于图的边控制数 12 图 2 6 可以分解为分别以为中心的个星图 12 k u uu k 若是树的符号边控制函数 对于连接边来说需要分两种情况讨论 fT i e 若 首先由定义知 1 i f e f 1 1 i iii eN e f ed ud uf e 有上边的不等式可知 为此我们构造以及 1 1 1 ii d ud u 1 ii G uu 同时重新定义符号边控制函数 1 ii G uu f 如图 2 6 所示 11 11 1 iiii iiii f eeTTu u fe eu wu w 图 2 7 在这里顶点数增加了 2 正边数增加了一条 同时 11 111 1 1 1 iiii iiiiiieN e eTTu u f e d ud ueu wu w 符合符号边控制函数的定义 若 且假设包含条这样的边 则直接删除边 我们有 1 i f e i e 11 1 iiii eN e f eeTTu u 符合符号边控制函数的定义 华东交通大学毕业论文 13 因为 则可知 那么 1 1 i iii eN e f ed ud uf e 1 0 0 ii d ud u 1 0 1 1 0 1 1 ii eN e ii eN e f ed uf e f ed uf e 或者 最后我们得到个星图及其符号边控制函数 由定理 2 2 可知1k 所以 1 0 1 Si Tik 01 1 ssssk TTTTk 最后得到定理结论 1 s T 同时 我们可以构造出一类图使得定理的等号成立 如图 2 7 所示 若树有则树满足以下条件 TV E 1 s T T 对于任意顶点 有 且为奇数 vV T d vn n 当时 含有两条悬挂边时 只有一条边标 另一条边标 3n 1 1 当时 含有悬挂边 且悬挂边标记为 非悬挂边标记为 3n 1 2 n 1 1 图 2 7 2 5 正则图的符号边控制数 引理 2 2 吉 9 任意一个都可以分解为一个和一1nkkG 阶边连通正则图1M 因子 个 21nkkG 阶边连通正则图 定理 2 6 任意有1nkkG 阶边连通正则图 刘峰 关于图的边控制数 14 2 2 21 s n kkn G k nk 当为奇数 当为偶数 证明 首先证明 设为一个的一个 2 21 s kn G k f1nkkG 阶边连通正则图SEDF 由的定义可知 对于 有都成立 且是正则图 由SEDF eE G 1 eN e f e G 的定义可知 设是一个 若对 s G s e E G Gf e G1nkk 阶边连通正则图 对于边 的闭邻域 有条边 在这些边中 我们至少要取 eE G e N e 21N ek 条边为 而剩余的 最多条 边为 如图 2 8 所示 k 1f e 1k 1f e 图 2 8 则有对于 有都成立 由此得到 eE G 1 eN e f e 1 2 212 212 21 s e E G knkkn kkn Gf e kkk AA 故 2 21 s kn G k 对于我们用数学归纳法进行证明 首先我们需要分两种情况 2 s n k G nk 当为奇数 当为偶数 分比别讨论初值成立 时 令 根据引理 2 2 知是一个 k当为奇数k当 3 GMG M1 因子 是一个 对此我们对于图定义二值函数 G2正则图Gf 1 1 eM f e eG 使得 华东交通大学毕业论文 15 如图 2 9 所示 1 3 eN e eG f e eM 图 2 9 从而是一个图的显然有 命题成立 fGSEDF 3 2 22 s n GE GMnn 时 令 根据引理 2 2 知是一个 k当为偶数k当 4 GMG M1 因子 是一个且无割边 对此我们对于图定义二值函数 G3正则图Gf 1 1 eM f e eG 使得 如图 2 10 所示 3 5 eN e eG f e eM 图 2 10 从而是一个图的显然有 命题成立 fGSEDF 4 2 2 s GE GMnnn 假设时命题也成立 即成立 且对于任意顶点1kl 2 s n k G nk 当为奇数 当为偶数 1vV Gdv 有 下面证明时命题也成立 设图是一个边连通 正则图 由于 因kl G1l l14l 此利用引理 2 2 两次可以把图分解为 其中和是两次分解中分别G GMMG M M 得到的 是最后一次得到的边连通正则图 同时可知 1 因子 G3l 2l 2 n MM 刘峰 关于图的边控制数 16 现在我们来定义为 首先由假设可知存在的为 则我们可以如SEDFf GSEDF f 下定义函数 f 1 1 feeG f eeM eM 因此当时 eE G 1221 eN eeE GeE MeE M f ef ef ef e 当时 记 eE M euv 1 21 eN eeE GeE MeE M f ef ef ef e d udv 当时 记 eE M euv 2 13 eN eeE GeE MeE M f ef ef ef e d udv 均有成立则 是的 同时又有 1 eN e f e fGSEDF 2222 22 ss e E M e E M nnnn n GGf ef e nn nnn 当为奇数 当为偶数 故当时命题也成立 kl 综上所述 命题结论成立 2 6 符号星控制数的界 定理 2 7 对于任意给定的图表示顶点的最大 GV G E GV Gn E Gm 度数 表示顶点的最小度数 则有成立 2 21 ss n m G 证明 取是图的 则对任意一条边有fGSSDF euvE G 华东交通大学毕业论文 17 1 eN e f ed udvf e 对上式遍历图的每条边进行求和G e E Ge E Ge E Ge E G eN e f ed udvf ed udvf e 注 每个顶点必须经历它在图中的算术顶点度数的统计 故上式等于G v V Ge E G d u d uf e 由的定义知道 故上式大于等于f 1 1d uf e 22 v V G d un mm 又 且 2 ss v V Gv V G d u d ud uG 1 eN e f e 所以 2 2 ss e E Gv V Ge E Ge E G ss Gf ed u d ud udvf e n Gm 故 成立 2 21 ss n m G 刘峰 关于图的边控制数 18 第三章 结 论 本课题研究的是图控制中的边控制理论 在研究的过程中 我们了解了图的一些控 制数的重要前沿理论 进一步地学习了数学思维的严谨性 同时系统地了解了图的基础 理论 掌握了图论的研究思想和方法 最后 也尝试提出自己的方法对已有的结果进行 重新论证 或者提出自己简单的猜想进行论证 最后得到结果 我们重新论证了常见图的一些符号边控制数的结论 设是一个星图 且 若为奇数则 若为偶数则 TV E E Tm m 1 s T m 2 s T 对任意一条路 那么它的符号边控制数由以下关系 2 m P m 1 2 0 mod3 3 1 2 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Pmm Pmm Pmm 对任意一个圈 那么它的符号边控制数由以下关系 m C 1 0 mod3 3 1 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Cmm Cmm Cmm 对任意一棵树 则有其控制数 TV E 1 s T 任意有1nkkG 阶边连通正则图 2 2 21 s n kkn G k nk 当为奇数 当为偶数 另外还提出了自己的结论且给出了详细证明 对于任意给定的图表示顶点的最大度数 GV G E GV Gn E Gm 表示顶点的最小度数 则有成立 2 21 ss n m G 华东交通大学毕业论文 19 第四章 谢 辞 值此论文完成之际 谨向给予我指导 关心和帮助的老师 同学 亲人朋友表示最 衷心的感谢 首先 向我的指导老师徐保根 刘二根老师表示衷心的感谢 在本科阶段的学习和 论文的撰写过程中 两位老师给予了我无私的指导和真诚的帮助 学习上 对我也是严 格要求 一丝不苟 而徐老师和刘老师在学术上的谦虚好学与严谨性 在教学上的认真 负责的风范更令我深深地折服 在课题研究的过程中得到了陈相兵 章志平 尹继昌 金科同学给予了我正确的指 正和帮助 使得本课题得以顺利完成 在此向他们表示感谢 感谢我的室友 谢谢他们在生活上和学业上给予我的关心和帮助 向百忙之中抽空评阅本论文的老师表示衷心的感谢 并感谢他们的宝贵意见 感谢所有的师长 感谢他们在我大学四年的路程中给予本人思想上 生活上 学业 上的教导 最后 我要感激我的父母和其他亲人所给予我的关怀和支持 刘峰 关于图的边控制数 20 参考文献 1 F 哈拉里 图论 M 上海科技出版社 1980 2 B Xu On signed edge domination numbers of graphs J Discrete Math 239 2001 179 189 3 B Xu On edge domination numbers of graphs J Discrete Math 249 2005 311 316 4 B Xu On Minus Domination and Signed Domination in Graphs J Journal of Mathematical Research then If is odd we may choose a function such that 1f e 2f E Tmm mf and then If is even the value is always even we 1 1 2 mm 1 s f E TT m2mm may choose a function such that and then f 1 2 2 mm 2 s f E TT Let The neighborhood subtree of is the subtree of whose edge set is eE T N TeTT and whose vertex set is the set of all end vertices of the edges of If is a pendant T Ne T Nee edge of then is the star whose central vertex is the vertex of having the degree greater T N Tee than 1 this is the maximal with respect to subtree inclusion subtree of of diameter 2 T containing In the opposite case is the maximal subtree of of diameter 3 whose central e N TeT edge is The set of all subtrees forwill be denoted by e N Te eE T N T Theorem 1 Let be a tree having the property that there exists a subsetof consisting of T 0 T N T edge disjoint trees whose union is ThenT s TT Proof Letbe the set of edges e such that For each the set is the set of 0 E 0 N TeT 0 eE T Ne neighbours of e and the union of all these sets is Thus is an edge dominating set in E T 0 ET Therefore 0 ET 刘峰 关于图的边控制数 24 Let be an SEDF of such that As the trees from are 1 1 fE T T s f E TT 0 T pairwise edge disjoint we have 00 0 1 sT ee E Tf E Tf NeET As for every tree T we have a corollary 1T Corollary 1 Let have the property from Theorem 1 ThenT 1 s T Conjecture For every tree we have T 1 s T By the symbol we denote the path of length i e with edges and vertices By m Pmm1m we denote the circuit of length m Cm Theorem 2 For the signed edge domination number on a path with m P2m we have 1 2 0 mod3 3 1 2 2 1 mod3 3 1 1 1 2 mod3 3 Sm Sm Sm Pmm Pmm Pmm Proof Let be an SEDF on such that Denote fP msm f E PP 1 m EeE Pf e Evidently each edge of must be adjacent to at least two edges of 1 m EeE Pf e E and each edge of is adjacent to at most one edge of By Proposition 2 between an E E E edge ofand an end vertex of there are at least two edges of and also between two E m PE edges of there are at least two edges of Hence andE E 1 2 3 Em If we choose one end vertex of and number the 1 22 2 3 m f E PEEmm m P edges of starting at it we may choose a function f such that if and only if the m P 1f a number of e is divisible by 3 and less than The and this is1m 1 2 2 3 m f E Pmm 华东交通大学毕业论文 25 And this number treted separately for particular congruence classes modulo 3 can be sm P expressed as in the text of the theorem As an aside we state an assertion on circuits its proof is quite analogous to the proof of Theorem 2 Theorem 3 For the signed edge domination number of a circuit we have m C 1 0 mod3 3 1 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Cmm Cmm Cmm Now we shall investigate caterpillars A caterpillar is a tree with the property that upon C deleting all pendant edges from it a path is obtained this path is called the body of the caterpillar Particular cases of caterpillars include stars and paths Let the vertices of the body of be C and edges for For let be the number of pendant edges 1 k uu 1ii uu 1 1ik 1 ik i p incident to The finite sequence determines the caterpillar uniquely From the i u 1 k i i p definition it is clear thatand If k 1 then such a caterpillar is a star If 1 1p 1 k p 1 1 k pp for then it is a path 0 i p 1 1ik Theorem 4 Let be a finite sequence of integers such that for 1 k i i p 1 2p 2 k p 1 i p Let be the number of even numbers among the 21ik 0 k numbers Let be the caterpillar determined by this sequence Then 121 1 1 kk pppp C 0 1 s Ck Proof The assumption of the theorem implies that each vertex of the body of is incident to at C least one pendant edge For let be the set of all edges incident to Let be a 1 ik i M i p i p vertex of the body of and let e be a pendant edge incident to it We have C i N eM We have for 11 1 k iiiiiij i ME C MMu uMM 2ij Hence The function f may be described in the following 1 1 11 kk iii ii f E Cf Mfuu 刘峰 关于图的边控制数 26 way If or then for exactly pendant edges e from if is even and 1i ik 1f e 1 2 i p i M i p for exactlyones if is odd If then for exactly pendant 1 1 2 i p i p21ik 1f e 1 2 i p edges e from if is even and for exactlyones if is odd For an edge e from the i M i p 1 1 2 i p i p body of always If or then for even and for C 1f e 1i ik 1 i f M i p 2 i f M odd If then for odd and for even We have i p21ik 1 i f M i p 2 i f M i p which implies the assertion 1 01 11 1 kk iii ii f Mkkf uuk Our considerations concerning will be finished by an existence theorem s T Proposition 4 Let be a graph with m edges and without a connected component isomorphic toG Then 2 K mod2 st Gm The proof is quite similar to the proof of Proposition 1 Proposition 5 Let be a graph without a connected component isomorphic to Let G 2 K 2N e for some edge Then for each eE G 1f x xN e The proof is straightforward This proposition implies two corollaries Corollary 2 Let be a path of length Then m P2m sm Pm Corollary 3 Let be a circuit of length m Then m C sm Cm Namely in both cases the unique SETDF is the constant equal to 1 Theorem 4 Let be a star with edges If m is odd then If m is even then T2m 3 st T 2 st T Proof Let be a SETDF such that Evidently there exists at least one edgef st f E TT such that We have and eE T 1f e E TN ee If m is even the value 2 can be attained by 1 12 st Tf E Tf N ef e constructing a SETDF such that for edges e and for edges f 1f e 1 1 2 m 1f e 1 1 2 m 华东交通大学毕业论文 27 If m is odd then according to Proposition 4 we have We may construct a SETDF f 3 st T such that f e 1 for edges e and for edges e 1 3 2 m 1f e 1 3 2 m We finish again by an existence theorem References 1 E Xu On signed domination numbers of graphs Discr Math submitted 2 T W Haynes S T Hedetniemi P J Slater Fundamentals of Domination in Graphs Marcel Dekker New York 1998 Author s address Bohdan Zelinka Technical University Liberec Voron ska 13 460 01 Liberec 1 Czech Republic e mail bohdan zelinka vslib cz 摘自 MATHEMATICA BOHEMICA 127 2002 No 1 49 55 刘峰 关于图的边控制数 28 B 外文翻译 译文部分 关于树的符号边控制数 Bohdan Zelinka Liberec Received April 18 2000 摘要 图的符号边控制数是随着符号控制数的变化而改变的一个变量 表示边 e 在图中的闭邻域 它是由边 e 和所有与 e 相邻的边组成的集合 假设函 G NeG 数是图的边集到集合的映射 如果对任意都有fG E G 1 1 eE G 成立的话 则称为图的符号边控制函数 同时在关于图的所有符号 1 x N e f x fGG 边控制函数中 得到的最小值 称作为图的符号边控制数 记为 f x E G f x G s G 同理 若用开邻域替闭邻域 我们得到图的符号全控制数的定 GG NeNee G NeG 义 我们把它记为 在这篇论文中研究的对象是树 st G 数表示的星图 路径 或者 毛虫树的符号边控制数 此外还有表示一 s T T sn C 个长度为 n 的圈的控制数 树满足不等式条件是确定的 对于给定边数 和 s TT 给定符号边控制数的树 已经证明了它的存在性定理 T 最后 得到了完全控制数的一些类似结果 st T 关键字 树 符号边控制数 符号全控制数 MSC 2000 05C69 05C05 在这里我们考虑的都是没有自环和没有重边的有限无向简单图 图的边集记为G 且顶点集记为 图的两条边称为邻边 如果他们是有一个共同顶点的 E G V GG 12 e e 两条不同的边 对于边的开邻域表示的是与边 相邻的所有边组成的集合 eE G G Nee 它的闭邻域则为 GG NeNee 如果我们考虑映射且当 我们记 1 1 fE G sE G x s f sf x 一个映射称为关于图的符号边控制函数 或全符号边控制函数 1 1 fE G G 华东交通大学毕业论文 29 如果 或分别成立 对任意一条边都成立 同时在关于 1 G f Ne 1 G f Ne eE G 图的所有符号边控制函数 或全符号边控制函数 中 得到的最小值 分Gf f E G 别称为图的符号边控制数 或符号边全控制数 关于符号边控制数在文献 B Xu 1 G 有介绍且记为 图的符号全控制数记为 s G G st G 符号边控制函数简记为 SEDF 全符号边控制函数简记为 SETDF 的值是随边 s G 控制数的变化而改变的一个边变量 2 另外还有一种有关图的控制数 是一个边集合映射到图的一个函数 当DG F G 的每一条边都在中时或者邻接于时 图的边集的子集称为中的边控GDDG F GDG 制数 若称是图的边控制函数 当的每一条边都在中或者邻接于 在图D F GGGDD 边控制集合中最小的边集数目就称为图的边控制数 记为 GG G 接下来我们研究的和都是关于树的结论 s G st G 引理 1 假设图有 m 条边那么G mod2 s Gm 证明 假设是的一个 SEDF 且 令 表示 或 fG s Gf E G mm 或 1f e 这类边的数目 我们有同时 因此 1f e mmm s Gmm 故结论成立 2 s Gmm 引理 2 若是树的 3 个顶点 且是的一个悬挂顶点 的两个邻接顶点分别 u v wTuTv 是 定义为的 SEDF 则有 u wfT 1f uvf vw 证明 我们知道且故结论成立 N uvuv vw f N uvf uvf vw 引理 3 若是一个星图 它含有条边 当为奇数时 当为偶数Tmm 1 s T m 时 2 s T 证明 在星图中所有的边都连接在一起 因此对任意一条边都 T NeE T eE T 成立若是的 SEDF 则有 故 设表示图中fT 1 T f E Tf Ne 1 s T m T 刘峰 关于图的边控制数 30 的边数 那么 如果为奇数时 我们可以取一个函数使得 1f e 2f E Tmm mf 满足 因此有 如果为偶数时 也是偶数我们可 1 1 2 mm 1 s f E TT m2mm 以选择一个函数使得 因此 f 1 2 2 mm 2 s f E TT 当 则的邻域子树 是由的顶点集 和的边集构成的图 eE T T N Te T Ne T Ne 若 是的一条悬挂边 那么是以边 的一个顶点为中心 且中心度数大于 1 的星图 eT N Tee 这就得到了包含边 且直径为 2 的最大生成子树 相反地是以边 为中心且直径为e N Tee 3 的最大生成子树 把所有的生成子树 其中 构成的集合记为 N Te eE T N T 定理 1 在树中存在一个的子集 满足所邻接的树的并是 则有T N T 0 T 0 TT s TT 证明 令是中的边集 对任意一条边 则集合是边 e 的邻域 0 E 0 N TeT 0 eE T Ne 集 且所有集合的并是 因此是的一个边控制集 因此有 E T 0 ET 0 ET 令是的一个 SEDF 所以 由于中的树是关联 1 1 fE T T s f E TT 0 T 我们有如下结论 00 0 1 sT ee E Tf E Tf NeET 我们已知对任意一个树都成立 所以有如下推论 1T 推论 1 当满足定理 1 的条件时 则有T 1 s T 猜想 对任意一个树 我们有成立 T 1 s T 表示长度为的路径 也就是说含有条边以及个顶点的路径 则表示 m Pmm1m m C 长度为的圈 m 定理 2 对于路径 它的符号边控制数有如下结论 m P2m 华东交通大学毕业论文 31 1 2 0 mod3 3 1 2 2 1 mod3 3 1 1 1 2 mod3 3 sm sm sm Pmm Pmm Pmm 证明 令是路径的 SEDF 则 取 f m P msm f E PP 1 m EeE Pf e 很明显对中任意一条边必须至少邻接两条中的边 且 1 m EeE Pf e E E 中的任意一条边至多只能邻接中的一条边 据引理 2 可知 的端点和的边之E E m P