首页 | 本学科首页   官方微博 | 高级检索  
     


Weighted domination in triangle-free graphs
Authors:Peter Dankelmann   Dieter Rautenbach  Lutz Volkmann  
Affiliation:

a School of Mathematical and Statistical Sciences, University of Natal, Durban 4041, South Africa

b Equipe Combinatoire, Université Pierre et Marie Curie, Paris, France

c Lehrstuhl II für Mathematik, RWTH Aachen, 52056 Aachen, Germany

Abstract:A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R>0. The weighted domination number γw(G) of (G,w) is the minimum weight w(D)=∑vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that
for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.
Keywords:Domination   Weighted graphs   Triangle-free graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号