• Title of article

    Special asteroidal quadruple on directed path graph non rooted path graph

  • Author/Authors

    Gutierrez، نويسنده , , Marisa and Tondato، نويسنده , , Silvia B.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2013
  • Pages
    6
  • From page
    47
  • To page
    52
  • Abstract
    An asteroidal triple in a graph G is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. A special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special connection. A special asteroidal triple play a central role in a characterization of directed path graphs by Cameron, Hoلng and Lévêque. They also introduce a related notion of asteroidal quadruple and conjecture a characterization of rooted path graphs. In this original form this conjecture is not complete, still in leafage four, as was showed in [M. Gutierrez, B. Lévêque, S. B. Tondato, Asteroidal quadruples in non rooted path graphs, manuscript 2012.] but as suggested by the conjecture, a characterization by forbidding particular type of asteroidal quadruples may holds. We prove that the conjecture in the original form is true on directed path graphs with leafage four having two minimal separators with multiplicity two. Thus we build the family of forbidden for this case.
  • Keywords
    asteroidal quadruples , clique trees , rooted path graphs
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Serial Year
    2013
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Record number

    1456408