天津科技大学学报
天津科技大學學報
천진과기대학학보
JOURNAL OF TIANJIN UNIVERSITY OF SCIENCE & TECHNOLOGY
2015年
4期
73-77
,共5页
有效符号边控制函数%有效符号边控制数%立方图
有效符號邊控製函數%有效符號邊控製數%立方圖
유효부호변공제함수%유효부호변공제수%립방도
efficient signed edge dominating function%efficient signed edge domination number%cubic graph
设G=(V,E)是一个非空图,若函数f:E→{?1,1}对?e∈E(G)均有∑e′∈N[e]f(e′)=1,则称f为图G的一个有效符号边控制函数. 图 G 的有效符号边控制数记为r′se (G) ,定义为r′se (G)=min{∑e∈E(G)f(e)|f 为图 G 的一个有效符号边控制函数}. 在本文中,我们给出了一般图的有效符号边控制数存在的必要条件和一个下界,并且证明了图 Pm×Cn不存在有效符号边控制函数,最后给出了立方图的有效符号边控制数存在的充要条件.
設G=(V,E)是一箇非空圖,若函數f:E→{?1,1}對?e∈E(G)均有∑e′∈N[e]f(e′)=1,則稱f為圖G的一箇有效符號邊控製函數. 圖 G 的有效符號邊控製數記為r′se (G) ,定義為r′se (G)=min{∑e∈E(G)f(e)|f 為圖 G 的一箇有效符號邊控製函數}. 在本文中,我們給齣瞭一般圖的有效符號邊控製數存在的必要條件和一箇下界,併且證明瞭圖 Pm×Cn不存在有效符號邊控製函數,最後給齣瞭立方圖的有效符號邊控製數存在的充要條件.
설G=(V,E)시일개비공도,약함수f:E→{?1,1}대?e∈E(G)균유∑e′∈N[e]f(e′)=1,칙칭f위도G적일개유효부호변공제함수. 도 G 적유효부호변공제수기위r′se (G) ,정의위r′se (G)=min{∑e∈E(G)f(e)|f 위도 G 적일개유효부호변공제함수}. 재본문중,아문급출료일반도적유효부호변공제수존재적필요조건화일개하계,병차증명료도 Pm×Cn불존재유효부호변공제함수,최후급출료립방도적유효부호변공제수존재적충요조건.
LetG=(V,E) be a graph.A function f:E→{-1,1} is to be anefficient signed edge dominating function of G,if ∑e′∈N[e]f(e′)=1 holds every edge e∈E(G). The efficient signed edge domination numberr′se (G)ofGis defined asr′se (G)=min{∑e∈E(G)f(e)|ffwhich is an efficient signed edge dominating function ofG}. 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 graphPm×Cn. Finally the sufficient and nec-essary condition is given for the existence of the efficient signed edge dominating function in a cubic graph.