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

On the total irredundant number of non-regular graphs

设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.