Weighted domination in triangle-free graphs

Peter Dankelmann, Dieter Rautenbach, Lutz Volkmann

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)233-239
Number of pages7
JournalDiscrete Mathematics
Volume250
Issue number1-3
DOIs
Publication statusPublished - 6 May 2002
Externally publishedYes

Keywords

  • Domination
  • Triangle-free graphs
  • Weighted graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Weighted domination in triangle-free graphs'. Together they form a unique fingerprint.

Cite this