• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 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

Global Defensive Alliances in Trees

Bouzefrane, Mohamed, Chellali, Mustapha, Haynes, Teresa W. 01 July 2010 (has links)
A global defensive alliance in a graph G = (V, E) is a set of vertices S ⊆ V with the properties that every vertex in V - S has at least one neighbor in S, and for each vertex v in S at least half the vertices from the closed neighborhood of v are in S. The alliance is called strong if a strict majority of vertices from the closed neighborhood of v are in S. The global defensive alliance number γa(G) (respectively, global strong defensive alliance number γâ(G)) is the minimum cardinality of a global defensive alliance (respectively, global strong defensive alliance) of G. We show that if T is a tree with order n ≥ 2, l leaves and s support vertices, then γâ (T) ≥ (3n - l - s + 4) /6 and γa (T) ≥ (3n - l - s + 4)/8. Moreover, all extremal trees attaining each bound are characterized.

Page generated in 0.0566 seconds