Domination in distance-hereditary graphs

Maw Shang Chang, Shaur Ching Wu, Gerard J. Chang, Hong Gwa Yeh

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs. In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case.

Original languageEnglish
Pages (from-to)103-113
Number of pages11
JournalDiscrete Applied Mathematics
Volume116
Issue number1-2
DOIs
StatePublished - 15 Jan 2002

Keywords

  • Distance-hereditary graph
  • Domination
  • Labeling
  • Leaf
  • Neighborhood
  • Twin

Fingerprint

Dive into the research topics of 'Domination in distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this