Abstract
A weighted graph (G, w) is a graph G together with a positive weight-function on its vertex set ir: V(G) -R>0. The weighted domination number >',(G) of (G,w) is the minimum weight ir(D) = £reon-(i') of a set D C V(G) such that every vertex .v V(D) - D has a neighbor in D. If -4rer(C)if(i')=|F(G)|, then we speak of a normed weighted graph. Recently, we proved that yw(G)y(G) < -4 (1 + -4] and >v(G) + -yn(G) -4 + 2(n"_2) for normed weighted bipartite graphs (G, w) of order n such that neither G nor the complement G has isolated vertices. In this paper we will extend these Nordhaus-Gaddum-type results to triangle-free graphs.
Original language | English |
---|---|
Pages (from-to) | 233-239 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 250 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 6 May 2002 |
Externally published | Yes |
Keywords
- Domination
- Triangle-free graphs
- Weighted graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics