图的有效符号边控制数  

Efficient Signed Edge Domination Number in Graphs

作　　者：张旭[1] 陈学刚[1,2] 

机构地区：[1]华北电力大学数理学院,北京102206 [2]北京工业大学应用数理学院,北京100124

出　　处：《天津科技大学学报》2015年第4期73-77,共5页Journal of Tianjin University of Science & Technology

基　　金：国家自然科学基金资助项目(10901051);北京市博士后工作经费资助项目

摘　　要：设G=(V,E)是一个非空图,若函数f:E→{-1,1}对?e∈E(G)均有∑f(e′)=1e′∈N[e],则称f为图G的一个有效符号边控制函数.图G的有效符号边控制数记为rs′e(G),定义为rs′e(G)=min{∑f(e)|f为图Ge∈E(G)的一个有效符号边控制函数}.在本文中,我们给出了一般图的有效符号边控制数存在的必要条件和一个下界,并且证明了图Pm×Cn不存在有效符号边控制函数,最后给出了立方图的有效符号边控制数存在的充要条件.Let G=（V,E）be a graph. A function f：E→{-1,1} is to be an efficient signed edge dominating function of G,∑f（e′）=1e′∈N[e] holds every edge e∈E（G）. The efficient signed edge domination number rse′（G） of G is defined rs′e（G）=min{∑f（e）｜f which is an efficient signed edge dominating function of G }. This paper firstly gives a necessary 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 Pm×Cn. Finally the sufficient and necessary 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

关 键 词：有效符号边控制函数 有效符号边控制数 立方图 

分 类 号：O157.5[理学—数学]