图的全符号局部控制数

上海大学学报(自然科学版) ›› 2009, Vol. 15 ›› Issue (3): 272-275.

图的全符号局部控制数

段铸荣1 高明晶2 高瑞平2

1.上海大学理学院,上海 200444; 2.河北科技师范学院数理系，河北秦皇岛 066004

收稿日期:2008-03-05 出版日期:2009-06-30 发布日期:2009-06-30
通讯作者: 段铸荣(1982～)，女，硕士研究生，研究方向为图论及组合最优化. E-mail:zhurong_1205@hotmail.com

Total Signed Local Domination Number in Graphs

DUAN Zhu-Rong-1, GAO Meng-Jing-2, GAO Rui-Beng-2

1.College of Sciences, Shanghai University, Shanghai 200444, China; 2.Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, Hebei, China

Received:2008-03-05 Online:2009-06-30 Published:2009-06-30

摘要/Abstract

摘要：

考虑图G=(V,E)均为不含有孤立点的有限简单连通图. f是一个从V∪E→{－1,1}的函数，记f的权为ω(f)=∑〖DD(X〗x∈V∪E〖DD)〗 f(x),对V∪E中任一元素x，定义f［x］=∑〖DD(X〗y∈〖WTBX〗N〖WTBX〗T(x)〖DD)〗f(y), NT(x)表示与x关联边、相邻点的集合. 图G的全符号局部控制函数为f:V∪E→{－1,1}, 满足对所有的x∈V∪E有f［x］≥1. 图G的所有全符号局部控制函数中最小的权定义为G的全符号局部控制数，记作γTsl(G). 得到在一般图中全符号局部控制数的下界和完全二部图Km,n中的上界，并求出圈Cn中γTsl的精确值. 

关键词: 完全二部图；圈；全符号局部控制数；下界；上界

Abstract:

The graphs G=(V,E) considered here are finite, simple and without isolated vertices. For a function f:V∪E→{－1,1},weight of 〖WTBX〗f〖WTBZ〗 is ω(f)=∑〖DD(X〗x∈V∪E〖DD)〗 f(x). For each element 〖WTBX〗x〖WTBZ〗 in V∪E, we define f［x］=∑〖DD(X〗y∈〖WTBX〗N〖WTBX〗T(x)〖DD)〗f(y), where 〖WTBX〗NT〖WTBZ〗(〖WTBX〗x〖WTBZ〗) denotes adjacent and incident element of 〖WTBX〗x〖WTBZ〗. A total signed local dominating function (TSLDF) of 〖WTBX〗G〖WTBZ〗 is a function f:V∪E→{－1,1} so that f［x］≥1 for all x∈V∪E. The total signed local domination number of 〖WTBX〗G〖WTBZ〗 is the minimum weight of a TSLDF on 〖WTBX〗G〖WTBZ〗, denoted by γTsl(G). In this paper, some lower bounds in general graphs and an upper bound in complete bipartite graph 〖WTBX〗Km,n〖WTBZ〗 for γTsl, and the exact value on γTsl of cycle 〖WTBX〗Cn〖WTBZ〗 can be obtained.

Key words: complete bipartite graph; cycle; total signed local domination number; lower bound; upper bound

中图分类号:

O157.5

段铸荣1 高明晶2 高瑞平2. 图的全符号局部控制数[J]. 上海大学学报(自然科学版), 2009, 15(3): 272-275.

DUAN Zhu-Rong-1, GAO Meng-Jing-2, GAO Rui-Beng-2. Total Signed Local Domination Number in Graphs[J]. Journal of Shanghai University（Natural Science Edition）, 2009, 15(3): 272-275.