 Pure Mathematics 理论数学, 2011, 1, 60-63 http://dx.doi.org/10.12677/pm.2011.12013 Published Online July 2011 (http://www.hanspub.org/journal/pm/) Copyright © 2011 Hanspub PM The Bound on Edge Domination Numbers of Graphs Jingjing C hen1, Chunxiang Wang2 1International Business Economic College of Wuhan Textile University, Wuhan 2School of Mathematics and Statistics, Huazhong Normal University , Wuhan Email: wcxiang@mail.ccnu.edu.cn Received Mar. 18th, 2011; revised May 4th, 2011; accepted May 6th 2011. Abstract: Let G be a graph without isolated vertices. A function : 1, 1fEG is called the signed edge domination function (SEDF) of G if 'eNe '1fe for every edge ()eEG . The signed edge domination number sG = min { GeE f ef |is an SEDF of G}. A function is called the signed star domination function (SSDF) of G if : 1,1G fE 1 vfe eE for every vertex . The signed star domination number = min { vVG G ss GeE f e | is an SSDF of G}.We prove that for any planar graph G of order n，. And we apply the property: If G is a connected cubic graph of f G s 1 n order n, then 7 16 G n , then we obtain that: For any cubic graph G of order n (), 1n sG n 8 5 . Finally for any 4-regular graph G of order n, 1 ss Gn if n is odd and ss G n if n is even. Keywords: Bound; Edge Domination Numbers; Cubic Graph 图的边控数的界 陈晶晶1，王春香 2 1武汉纺织大学外经贸学院，武汉 2武汉华中师范大学，武汉 Email: wcxiang@mail. ccnu.edu.cn 收稿日期：2011 年3月18 日；修回日期：2011 年5月4日；录用日期：2011 年5月6日 摘 要：令G是一个没有孤立点的图。函数 :fEG1,1, 1 如果对每条边 ， ，则 称为符号控制函数。 eEG 'eNe 'fef sG = min{ eEG f e | 是G的符号边控制函数} 称为符号控制数。函数 如果对每个点 f :fEG1,1, ，vVG eEv f e 1，则称 f为符号 星控制函数。符号星控制函数记为 ss G = min { eEG f e |f 是 G 的符号星控制函数}。我们利 用平面图的特性得到：对任何 n阶平面图 G有 s G 1, 1nn 。同时利用连通 3-正则图中 7 'G 16 n得到：如果 G是n点连通的 3-正则图( )，则1n sG n 8 5 。最后，对任何 4-正则图 G有 点，如果 是奇数，则；如果 是偶数，则 n n 1 ss Gn n ss G n 。 关键词：界；边控数；3-正则图 1. 引入 本文讨论有限、无向、简单图(无环、无重 边)。 在以下论文中若没有出现的记号和术语我们采用文献 集合和边集合。如果 [1]中的记号和术语。V(G)和E(G)分别表示图 G的点 xy E(G)，则称 x和y相邻。对 于G的子图 H，NH示x在H中的邻点集合， 且 )(x表 HH dx Nx在H中的度。如果上下文不表示 x 发生混淆， Nx和 dx分别代替 H Nx 和 H dx 。  陈晶晶 等图的边控数的界61 | G中剖分一条 –e + vx + v通过剖分边 在图 边exy是指在 G中加入一个新点 v，令 'G=G，我们称是 e 得到的图。对于 , y 'G A B，E(A, B)表示一个端点 在A中另一个端点在 B中的边的集合。 e(A, B)=|E(A, B)|. 令e(G)表示图 。当 A = {a}，e(a, B)(= B da) = e(A, B)。对于 V 中的边 G G数 令 euv EG ， G Ne{ 'eEG|'e和e有一个公共的端点}称为 G中的边的边邻域。 e在图 G e e称 G中 G Ne为 G域。如果 )(GVv，则 | GvuvEGvVG 的开 邻域。 N e在图 e E 边 在图 中的闭的边邻 称为 G Ne和 G Ev分别简记为 Ne和 。 Ev 令图 G = (V, E)， M E G的 饱和 ，如果 M中任何两条边 不相邻，则 为匹配。如果 关联 M称M图点 v匹配 中某个边，则称匹配 M点v，或点v被M-饱和， 否则 v称为M-不饱和点。如果G中所有点都是M-饱 和的，则匹配 M称为完美匹配。如果G中没有匹配' M 使得 ,MM 则M称为图 G的最大匹配。记 G' 为图 G中最大匹配 M中的边数。 定义 G是一个图，函数 : 1 [2]令 f EG 1 , 1, 如果对每条边 eEG 数。 ， eN '1fe，则 f称为符号控 m e' sG = 制函 in{ eeN f e|f是G的符号 数} 制数。 义2 [3 没有孤立点的图。函数 :1, 1,fEG 如果 控 令个 对 的符号 ] 边控制函 称为图 G 定G是一 每个点 GVv， () () 1 Evfe ，则称 f为符号星控制函数。符号星 = min{ eEG e 控制函数记为 ss G f e |f是G的 提出下列猜想 1。 图 符号边控制函 符 在文献[3] ogen Xu： 猜想 G是n点图 号星控制 3-正 2. 主 引理 函数} 1 令 。 中，B ) T是 则 eET a (1n n点树， 有s 它的任何 1 Gn 在这篇文章中，我们证明这个猜想对于平面和 则图是成立的。 要结论 数f都满足 f en 。 证明 我们定义树 T的函数， :1, 1,fET 令 1, f eeT的EfT，显然是符号边控制函数 且 1 eET f en 。因此，对 T 函数 1 f有 的任何符号边控制 TeE f en。 面图 G，有不等式定理 2 任何n点平 1 sGn 成立。 证明 不失一般性，假定G连通。否 G的每个 则我们考虑 连通分支。令 G有 个面。如果 1 ，由 引 理1，结论显然成立。下面设 2 。令 01 1 ,,,fff 是一个面的序列满足 i f和 10,1,,,1i 有公共边 2 i f 1 0,1, ,2, i ei ，其中 1 e 是0 f 和 1 f 的公共边。如果 1 是偶数，令 1,3, ,2. jj Ce 如果 1 是奇数，令 1,3, ,1. jj Ce显然 1 2 C 。 定义函数 :1fEG,1,令 1, f eeC和 ' \'1, f eeEG C .对任何点 vVG，令 E v ,e EG和|1efe v efe|1,E eEG 此对任何点 。既然任何一个面至多 赋–1有一条边 ，因 vVG，则 有 E –1 的边，有 1 eNefe v Ev 。从 而对 任何一条赋 成立，对任何 赋1的边，有 fe1 eNe 成立。因此 f是G的符 号边控制函数。故 sG eG 21 eG C 式 既 然G是平面图，由 有 2neG .故欧拉公 1 sGn 。 引理 3 [4] 如果 G是n点连通则的 3-正则图， 7 '16 如果 n图 Gn 定理 4G是点连通的 3-正则 ，则 。 (1n) 5 8 是G sGn 。 证明 令M的极大匹配。由引理3， 7 16 n。定义 G的函数 ,1,1: GEf M 令 1, f eeM和 , '\'1 f eeEGM 。如果 Me ，则 '' '' eNe fe 4 131 。如果 \eEGM，则 ''eNe fe ''3 21 。因此，f 符号边控 ，故 是G的制函数。既然 G是3-正则图 13 xVG eGx n 。 从而 22 d 375 2 2168 sGn n 引理 5 每一个2-边连通的 3-正则图有完美匹配。 6 如果 G是n阶3-正则图 且至多一 条割 n。 定理 (1n) 边，则 1 2 sGn 。 证明 分下列两种情形： Copyright © 2011 Hanspub PM  陈晶晶 等图的边控数的界 62 | G的函数 1,令 情形 1. G有完美匹配 P。 定义 :1, fEG 1, f eeP和 '1, '\ f eeEGP 。如果 4131Pe，则 eNe fe 。如 \eEGP，则 果 321。因此， []eNe fe f 是G的符号边控制函数。从而 31 2 22 s1 2 nn 由引理 5，G有割边，设割边 Gn 情形 2. G没有完美匹配。 xy e 12 ,,xx y ，由条件知， 图G割边唯一。令 和 Nx Ny 1 ,, 2 y yx。用 21 , x yxy 取代 Ne中边 21 , x xy ' y使得 完美匹配所得图 'G ' 是3-正则的2-边连通 G图。 则 P 。定义'G的符号边控制函数 ': 'fEG 1,1,令 '1,' f ee 数 P和fe G的一个函 ''1,' ' \eEG'P，则得到 :1,,1fEG 令 ' f efe 21 ,\eEG x xy 2 fxy和x 2 ' f xy ， 1 fyy 1 ' f xy 。既 然'G是3-正则的2-边连通图，因此 'G有 完美匹配 ' P ，由情形 1知， 311 '2 22 2 sGn nn 。 既然 2 eEG eEG n fefe ，故我们只需证 的符 。 断言 f是G的符号边控制函数。 三种情形： 子情形 2.1 ，或，属于 明f是G号边控制函数 证明：分 1 2 xyyy (1 xx yx2)' P 。 从上面的运算可知， f uvf uv 对所有的边 uvE GNe fyy fyy ，且 12 fxx fxx 当 2 1fxx 。 ， 12 1 11 E G ',ePxyyy 321 。 时，则 ''eNe fe fNxy321， 12 x4131，fNxxfNx 1 fNyy 232fNyy 1。因此 控制函数。f是G的符号边 子情 1 形2.2 ，或，属于 1 xx 2 yy (xy yx2)' P 。 由上面的运算， ， 1 12 1fxx fyy ， 21fxx fxy fyy f uvf uv ，对所 有的边 uvE GNe。令 : M uvE G 的完美匹配，这与情形 2 1fuv ，则 M是G中 G没有完美匹配相矛盾。 子情形 2.3 xy 属于 。 从上面的运算可知， 'P 121 fxx fyyfyy 21fxx ， 1fxy ， f uv ' f uv ，对uv EG Ne。令 :1MuvEGfuv ，则 M 函数。 是G 因此 的完美匹配， 中G这与情形 2没有完美匹配相矛盾。 的符号边控制从上面的断言可知，f是G 1 2 如果 G s Gn。 是通过剖分边 ',ee 得到的图，剖分点记为 x 和'x，且 , G dxx k ，则我们称两条边,ee 的距 离为 e ,1k G de 。 (n推论 7 条边 'e n点1) 3-正则图G，如果任何两 对于 e和 足满 ,5dee 则1 2 Gn 。 定理 ( s 1) k-正则8 对于 有不等n点n图G， 式 4 sk e 2k 成立。 Gn 任 G的符证明 令f是号边控制函数。对 何边 uv ，既然 e 1 eNe f ，则在e的闭邻域中至 多 1 k1 2 dudv 条边赋值为–1。如果我们记 数所有边的闭邻域，则赋值为–1 的边至多出现 1 2 nk k 次。但是，的边重复记数为 12赋值为–1 k 此至多 次，因 1 22 nk k k1 条边 –1赋值为 ，故 1k 2 222142kk snk G nk kn 推论 9 对于n图G，有 3 1 sGn 。 点3-正则 0 引理 10 [3] 任何 n点图 有 满足 G 1, 2 ss n G 。 G有完美 则有 定理 11 对n点3-正则图 G，如果 ， 匹配 2 n G ss 。 定理 12 n点4-正则 n是奇对 图G，如果 数，有 1n；如果n是偶数 ss Gn 。 ss G 4dv 证明 既然 ，，与 至多一条边赋值为 一条边相邻两 点， 对所有点 –1。既然 vVGv相 个 邻的边中 则至多 2 n 条边赋值为–1，因此， 22 2 n ， ss n G Copyright © 2011 Hanspub PM  陈晶晶 等 | 图的边控数的界 Copyright © 2011 Hanspub PM 63 n；如果 偶数 。 参考文献 (References) [1] Graph theory with applications. altham: Acess, 1976. 189. crete Mathematics, 1982, 42: [2] B. Xu. On signed edge domination numbers of graphs. Discrete Mathematics, 2 001, 239(1-3): 179- 即：如果 是奇数，有 1 ss Gn n是 ss Gn J. A. Bondy, U. S. R. Murty. Wademic Pr [3] B. Xu. On edge domination numbers of graphs. Discrete Ma- thematics, 2005, 294(3): 311-316. [4] A. M. Hobbs, E. Sch meichel. On the maximum number of inde- pendent edges in cubic graphs. Dis 317-320. |