• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

H-forming Sets in Graphs

Haynes, Teresa W., Hedetniemi, Stephen T., Henning, Michael A., Slater, Peter J. 06 February 2003 (has links)
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.

Page generated in 0.0729 seconds