H-forming sets in graphs

Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning, Peter J. Slater

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

For graphs G and H, a set S⊆V(G) is an H-forming set of G if for every v∈V(G)-S, there exists a subset R⊆S, where |R|=|V(H)|-1, such that the subgraph induced by R∪{v} contains H as a subgraph (not necessarily induced). The minimum cardinality of an H-forming set of G is the H-forming number γ {H}(G). The H-forming number of G is a generalization of the domination number γ(G) because γ(G)=γ {P2}(G) . We show that γ(G)γ {P3}(G)γ t(G), where γ t(G) is the total domination number of G. For a nontrivial tree T, we show that γ {P3}(T)=γ t(T). We also define independent P 3-forming sets, give complexity results for the independent P 3-forming problem, and characterize the trees having an independent P 3-forming set.

Original languageEnglish
Pages (from-to)159-169
Number of pages11
JournalDiscrete Mathematics
Volume262
Issue number1-3
DOIs
Publication statusPublished - 6 Feb 2003
Externally publishedYes

Keywords

  • Domination
  • H-forming number
  • Independence
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'H-forming sets in graphs'. Together they form a unique fingerprint.

Cite this