Trees with equal average domination and independent domination numbers

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

For a vertex D of a graph G = (V,E), the domination number γv(G) of G relative to v is the minimum cardinality of a dominating set in G that contains v. The average domination number of G is γav(G) = 1/|V| ∑v∈V(G). The independent domination number iv(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average independent domination number of G is iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that a tree T satisfies γav(T) = iav(T) if and only if A(T) = Φ or each vertex of A(T) has degree 2 in T, where A(T) is the set of vertices of T that are contained in all its minimum dominating sets.

Original languageEnglish
Pages (from-to)305-318
Number of pages14
JournalArs Combinatoria
Volume71
Publication statusPublished - Apr 2004
Externally publishedYes

Keywords

  • Average domination
  • Average independent domination
  • Trees

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Trees with equal average domination and independent domination numbers'. Together they form a unique fingerprint.

Cite this