PDF《图的有效符号边控制数》

第30 卷第4期2015 年8月天津科技大学学报 Journal of Tianjin University of Science &

Technology Vol.

30 No.

4 Aug.

2015 收稿日期:2014C06C17;

修回日期:2014C07C14 基金项目:国家自然科学基金资助项目(10901051);

北京市博士后工作经费资助项目 作者简介:张旭(1989―),女,河北人,硕士研究生;

通信作者:陈学刚,教授,[email protected]. DOI:10.13364/j.issn.1672-6510.20140094 图的有效符号边控制数 张旭1,陈学刚 1,2 (1. 华北电力大学数理学院,北京 102206;

2. 北京工业大学应用数理学院,北京 100124) 摘要:设(),GVE=是一个非空图, 若函数 { } : 1,1 f E → ? 对()eEG?∈均有 ( ) [ ]

1 e N e f e ′∈ ′ = ∑ , 则称 f 为图 G 的一个有 效符号边控制函数. 图G的有效符号边控制数记为 ( ) se r G ′ , 定义为 ( ) min se r G ( ) e E G f e ∈ ∑ |f 为图 G 的一个有效符号 边控制函数}. 在本文中, 我们给出了一般图的有效符号边控制数存在的必要条件和一个下界, 并且证明了图 m n P C * 不存在有效符号边控制函数, 最后给出了立方图的有效符号边控制数存在的充要条件. 关键词:有效符号边控制函数;

有效符号边控制数;

立方图 中图分类号:O157.5 文献标志码:A 文章编号:1672-6510(2015)04-0073-05 Efficient Signed Edge Domination Number in Graphs ZHANG Xu1 ,CHEN Xuegang1,

2 (1. Department of Mathematics and Physics, North China Electric Power University, Beijing 102206, China;

2. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China) Abstract:Let ( ) , G V E = be a graph. A function { } : 1,1 f E → ? is to be an efficient signed edge dominating function of G , if ( ) [ ]

1 e N e f e ′∈ ′ = ∑ holds every edge ( ) e E G ∈ . The efficient signed edge domination number ( ) se r G ′ of G is defined as ( ) min se r G ( ) e E G f e ∈ ∑ | f which is an efficient signed edge dominating function of G }. This paper firstly gives a nec- essary condition for the existence of an efficient signed edge domination number and a lower bound on the general graph. Secondly it shows that there is no efficient signed edge dominating function of graph m n P C * . Finally the sufficient and nec- essary condition is given for the existence of the efficient signed edge dominating function in a cubic graph. Key words:efficient signed edge dominating function;

efficient signed edge domination number;

cubic graph

2001 年, 徐保根[1C2] 提出了图的符号边控制概 念, 获得了符号边控制数的许多界限, 并将这一概念 推广到边上的多种符号控制, 如符号星控制、 符号圈 控制、 符号团控制、 符号路控制等等. 关于边控制, 文献[3C9]做出了一些重要结论, 尤其是文献[9], 得到了 图的符号边控制数的一个新的下界, 并确定了圆梯

2 n P C * 的符号边控制数. 文献[10]主要研究了图的有 效减控制和符号控制. 文献涉及到图的有效符号边控 制数的研究很少, 本文在参考文献[9]和[10]的基础 上, 研究图的有效符号边控制数. 首先考虑非空图 G 存在有效符号边控制函数的必要条件和下界, 然后讨 论图 m n P C * 是否存在有效符号边控制函数, 最后研究 立方图存在有效符号边控制函数的充要条件.

1 概念本文中所指的图均为无向简单图, 文中未说明的 符号和术语同于文献[1]. 设(),GVE=为一个图, ( ) V V G = 和()EEG=分别表示其顶点集和边集. 若eE∈,则()GNe表示 G 中与e相邻的边集,称 为e的边邻域;

[]GNe=(){}GNee∪称为 e 的闭边邻域. | | G G d e N e = 表示 G 中与 e 相邻的边的条数, 称为 e 在G中的边度. 在・74・ 天津科技大学学报 第30 卷第4期不引起混淆的情况下, [ ] G N e 、 ( ) G N e 和()Gde可分别 简记为[]Ne、()Ne和()de.若()euv E G = ∈ , 则2dedudv=+?.设ME?,若M中任两边的 距离至少为 2, 则称 M 为G的一个导出匹配. 在G中, n P 和nC分别表示 n 个点的路和圈. 假设 G 是一个 图, 则G 的对偶图G′ 的构造方法为: 把G 中的边对应 成G′ 中的顶点, G′ 中的两点相邻当且仅当它们的对 应边在G 中相邻. 定义设(),GVE=是一个非空图,若 函数{}:1,1 f E → ? 对()eEG?∈均有 ( ) [ ]

1 e N e f e ′∈ ′ = ∑ , 则称 f 为图 G 的一个有效符号边控制函数. 图G的有效 符号边控制数记为()se r G ′ , 定义为()min se r G ( ) e E G f e ∈ ∑ | f 为图 G 的一个有效符号边 控制函数}. 设R是一个实数集, 对实值函数 : f E R → 和非 空子集 ( ) S E G ? , 记()()eSfSfe∈=∑.为简单起见, 把 满足 ( )

1 f e = + 的边 e 称为

1 + 边, 把满足 ( )

1 f e = ? 的边e称为

1 ? 边.

2 主要结果及证明 2.1 图的有效符号边控制数存在的必要条件和一个 下界 定理

1 设(),GVE=是一个非空图, 若G存在 一个有效符号边控制函数,则对()eEG?∈均有()()0mod

2 d e ≡ . 证明 设f为图 G 的一个有效符号边控制函 数, 且使得 ( ) ( ) se r G f E ′ = .令()(){}1|1EeEGfe=∈=,()(){}2|1EeEGfe 对()eEG?∈,若e邻接

1 E 中边的个数为s,则e邻接2E中边的个数为()des?.由于()[]()()()1eNefesdesfe′∈ ∑ ,从而()()12defes+?=.当 ( )

1 f e = 时,()2des=;

当 ( )

1 f e = ? 时,()22des+=.因 为s为整数,所 以()()0mod

2 d e ≡ . 定理

2 设G是一个 n 阶连通图,m 为G的边 数,若G存在一个有效符号边控制函数,则有()21se m r G m δ δ ′ ? Δ + ? ≥ , 其中 Δ 和δ 分别为图 G 的最大 度和最小度. 证明 设f为图G 的一个有效符号边控制函数, 且使得()()se r G f E ′ = . 令()(){}1|1EeEGfe=∈=,()(){}2|1EeEGfe1Ep=和2Eq=.显然 m p q = + .又由于[]()()()11eEeEmfNede∈∈==+?∑∑()()()()(())212(()1)

1 1 e E uv E uv E d e d u d v d u d v ∈ ∈ ∈ ∑ ∑ ∑ ≤ ( ) ( )

1 2

2 1

2 1 E E δ Δ

2 1

2 1 p q δ = Δ

2 1 = Δ ? ? ( )( )

2 1 p m p δ ? ? ? . 所以

1 m p δ δ Δ + ? ≥ . 因此 ( ) se r G ′ =

2 2

1 m p m m δ δ ? ? Δ + ? ≥ . 推论

1 设G是边 r ? 正则图,m 为G 的边数, 若G存在一个有效符号边控制函数,则()1se m r G r ′ = + . 证明 由定理

2 的证明过程可知 [ ] ( ) ( ) ( ) ( ) ( )

1 2

1 1 e E e E e E m f N e d e d e ∈ ∈ ∈ ∑ ∑ ∑ ( ) ( )

1 2

1 1 e E e E r r ∈ ∈ + ? +

1 2

1 E E r = ? + . 所以 ( )

1 2

1 se m r G E E r ′ = ? = + . 推论

2 n 阶圈 n C 存在有效符号边控制函数 ( )

0 mod3 n ? ≡ . 2.2 图*mnPC的有效符号边控制函数的研究 参考文献[9]的定理

2 主要研究了圆梯

2 n P C * 的 符号边控制数, 下面讨论图 m n P C * 的有效符号边控制 函数的存在性. 定理

3 设mnGPC=*()2,

3 m n ≥ ≥ , 则图 G 中 不存在有效符号边控制函数. 证明 (1)当mnGPC=*()3,

3 m n ≥ ≥ 时, 给G标号 {

11 12

1 21

22 n u u u u u }

2 1

2 n m m mn u u u u , 如图

1 所示. 图1mnGPC=*Fig.

1 m n G P C = * 容易看出, ( )

1 2

5 i i d u u = 为奇数, 其中 1,2, , i n = . 所以, 由定理

1 可得图 G 中不存在有效符号边控制 函数.

2015 年8月张旭,等:图的有效符号边控制数 ・75・ (2)当2nGPC=*()3n≥ 时, 给G标号为 {

1 2 , , u u }

1 2 n n u v v v , 可以看出 ( )

4 d e = ( ) ( ) e E G ? ∈ , 如图2所示. 采用反证法来证明. 图22nGPC=*Fig.

2 2 n G P C = * 假设图G 中存在有效符号边控制函数, 下面分

3 种情况来讨论. 情况

1 ( ) ( )

1 1

1 i i i i f u v f u v 如图

3 所示. 图3情况

1 Fig.

3 Situation

1 由()[]11iieNuufe?′∈ ′ = ∑ 得()()211iiiifuufuu???==()11iifuu+=+.由()[]11iieNvvfe?′∈ ′ = ∑ 得()()211iiiifvvfvv???==()11iifvv+=+.此时, ( ) [ ]

3 1 i i e N u v f e ′∈ ′ = ∑ >

, 矛盾, 所以假 设不成立. 情况

2 ( ) ( )

1 1

1 i i i i f u v f u v 如图

4 所示. ① ② 图4情况

2 Fig.

4 Situation

2 ① 当()11iifuu?=?时,由 ( ) [ ]

1 1 i i e N u u f e ? ′∈ ′ = ∑ 得()211iifuu??=+且()11iifuu+=?或()211iifuu??=?且()11iifuu+=+.不失一般性, 假设 ( )

2 1

1 i i f u u ( )

1 1 i i f u u + = ? . 由()[]1iieNuvfe′∈ ′ = ∑ 得()1iifvv?=()11iifvv+=+,此时 ( ) [ ]

1 1 i i e N v v f e ? ′∈ ′ ∑ >

, 矛盾. ② 当()11iifuu?=+时, 则()11iifvv?=+(否则同 上, 矛盾). 因为 ( ) [ ]

1 1 i i e N u u f e ? ′∈ ′ = ∑ , 所以 ( )

2 1 i i f u u ? ? = ( )

1 1 i i f u u + = ? . 由()[]1iieNuvfe′∈ ′ = ∑ 得()11iifvv+=?.又由()[]111iieNuvfe++′∈ ′ = ∑ 得

1 1

1 2

1 2 i i i i i i f u v f u u f v v = = =

1 + , 此时 ( ) [ ]

1 1 i i e N v v f e + ′∈ ′ ∑ >

, 矛盾. 所以, 假设不成立. 情况

3 ( )

1 1 1, i i f u v

1 i i f u v = ? , 如图5 所示. ① ② 图5情况

3 Fig.

5 Situation

3 由情况1和情况2知()221iifuv ( )

1 1

1 i i f u v ① 当()11iifuu?=?时,由 ( ) [ ]

1 1 i i e N u u f e ? ′∈ ′ = ∑ 得()()211iiiifuufuu??+=1=+.又 由()[]1iieNuvfe′∈ ′ = ∑ 得()11iifvv+=+.因为()[]11iieNuufe+′∈ ′ = ∑ , 所以()121iifuu 此时 ( ) [ ]

1 1

1 i i e N u v f e + + ′∈ ′ ∑ >

, 矛盾. ② 当()11iifuu?=+时,由 ( ) [ ]

1 1 i i e N u u f e ? ′∈ ′ = ∑ 得()211iifuu??=+且()11iifuu+=?或()21iifuu??=1?且・76・ 天津科技大学学报 第30 卷第4期()11iifuu+=+.不失一般性, 假设 ( )

2 1

1 i i f u u ( )

1 1 i i f u u + = ? . 因为 ( ) [ ]

1 i i e N u v f e ′∈ ′ = ∑ , 所以 ( )

1 i i f v v ? = ( )

1 1 i i f v v + =+ . 由()[]11iieNvvfe?′∈ ′ = ∑ 得()211iifvv 又由()[]211iieNuufe??′∈ ′ = ∑ 得()321iifuu此时()[]221iieNuvfe??′∈ ′ ∑ <

, 矛盾. 所以假设不成立. 综上, 定理

3 成立. 2.3 立方图的有效符号边控制数 由定理 3, 不是每个图都存在有效符号边控制函 数, 下面讨论具有什么结构的立方图存在有效符号边 控制函数. 引理

1 Petersen 图的有效符号边控制数存在且 ( )

3 se r G ′ = . 证明对Petersen 图G的顶点标号为{}1210 , , , v v v , 如图

6 所示. 定义 Petersen 图的有效 符号边控制函数f如下:()15fvv=()34fvv=()()3816fvvfvv==()79fvv=()710

1 f v v = ? , 其他各边 的函数值都为1+.此 时对()eEG?∈都有()[]1eNefe′∈ ′ = ∑ . 所以 Petersen 图存在有效符号边控制 函数. 因为 ( ) e E G ? ∈ 都有 ( )

4 d e = , 所以 Petersen 图是一个边4?正则图.根据推论1可得()se r G ′ =

3 1 m r = + . 图6Petersen图Fig.

6 Petersen Graph 下面给出立方图 G 存在有效符号边控制函数的 充要条件. 定理

4 设G 是一个立方图, ( ) , G V E ′ ′ ′ = 是G 的 对偶图, 则G存在有效符号边控制函数的充要条件 为G′ 中存在一个导出匹配 M , 使得 ( ) G V V M ′ ′ ′ ? ? ? ? ? 是圈的并. 证明 因为 G′ 中存在一个导出匹配 M , 使得 ( ) G V V M ′ ′ ′ ? ? ? ? ? 是圈的并. 定义函数 { } : 1,1 f V ′ → ? 如下: ( ) ( ) 1, 1, v M f v v V V M ? ? ∈ ? ? = ? ′ ′ + ? ∈ ? ? ? 易证 f 为G′ 的一个有效符号控制函数, 所以 G 存在有效符号边控制函数. 若立方图存在有效符号边控制函数, 则G的对 偶图 G′ 就存在有效符号控制函数, 即对 ( ) v V G′ ? ∈ 均有 ( ) [ ]

1 v N v f v ′∈ ′ = ∑ . 又[]||5Nv=,所以 [ ] N v 中有

2 个 点标号为

1 ? ,

3 个点标号为

1 + . 对每个

1 ? 点来说,........