关于非正则图的全无赘数的上界(英文)  

On the total irredundant number of non-regular graphs

作　　者：华洪波[1] 邓汉元[1] 

机构地区：[1]湖南师范大学数学系,湖南长沙410081

出　　处：《湖南文理学院学报（自然科学版）》2004年第2期2-3,11,共3页Journal of Hunan University of Arts and Science(Science and Technology)

基　　金：theChinaNationalScienceFoundation[10 2 710 45]andtheEducationCommitteeofHunanProvince

摘　　要：设G =(V ,E)是一个无向图 ,如果S V ,对于任v∈V ,均有v或者它的一个邻点在S -v中没有邻点 ,则称S为G的一个全无赘集 .G中含点数最多 (少 )的极大全无赘集 ,称为上全无赘集 (全无赘集 ) .G的 (上 )全无度Δ(G)给出全无赘数的上界 ,IRt(G) n1+(Δ +1)δ(Δ - 1)Δ而且这个界可达 .Let G=(V,E) be an undirected graph,a set S of vertices in the graph G is called a total irredundant set if,for every vertex v in G,v or one of its neighbors has no neighbor in S-{v}.The total irredundance number ir t(G) is the minimum cardinality of any total irredundanct set,while the upper total irredundance number IR t(G) is the maximal cardinality of any such set.In this paper,we give a upper bound of IR t(G) for a non-regular connected graph G in terms of maximum degree Δ(G),minimum degree δ(G) and its order n.We show that IR t(G)n1+(Δ+1)δ(Δ-1)Δ and the bound is sharp.

关 键 词：非正则图 全无赘数 上界 无向图 

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