• Title of article

    The intersection of all maximum stable sets of a tree and its pendant vertices

  • Author/Authors

    Vadim E. Levit، نويسنده , , Eugen Mandrescu، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2008
  • Pages
    6
  • From page
    5809
  • To page
    5814
  • Abstract
    A stable set in a graph image is a set of mutually non-adjacent vertices, image is the size of a maximum stable set of image, and image is the intersection of all its maximum stable sets. It is known that if image is a connected graph of order image with image, then image, [V.E. Levit, E. Mandrescu, Combinatorial properties of the family of maximum stable sets of a graph, Discrete Applied Mathematics 117 (2002) 149–161; E. Boros, M.C. Golumbic, V.E. Levit, On the number of vertices belonging to all maximum stable sets of a graph, Discrete Applied Mathematics 124 (2002) 17–25]. When we restrict ourselves to the class of trees, we add some structural properties to this statement. Our main finding is the theorem claiming that if image is a tree of order image, with image, then at least two pendant vertices an even distance apart belong to image.
  • Keywords
    Tree , Pendant vertex , Maximum stable set , Core
  • Journal title
    Discrete Mathematics
  • Serial Year
    2008
  • Journal title
    Discrete Mathematics
  • Record number

    947201