Asteroidal Quadruples in non Rooted Path Graphs

Marisa Gutierrez; Benjamin Lévêque; Silvia B. Tondato

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 603-614
  • ISSN: 2083-5892

Abstract

top
A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.

How to cite

top

Marisa Gutierrez, Benjamin Lévêque, and Silvia B. Tondato. "Asteroidal Quadruples in non Rooted Path Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 603-614. <http://eudml.org/doc/275861>.

@article{MarisaGutierrez2015,
abstract = {A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.},
author = {Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {clique trees; rooted path graphs; asteroidal quadruples},
language = {eng},
number = {4},
pages = {603-614},
title = {Asteroidal Quadruples in non Rooted Path Graphs},
url = {http://eudml.org/doc/275861},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Marisa Gutierrez
AU - Benjamin Lévêque
AU - Silvia B. Tondato
TI - Asteroidal Quadruples in non Rooted Path Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 603
EP - 614
AB - A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.
LA - eng
KW - clique trees; rooted path graphs; asteroidal quadruples
UR - http://eudml.org/doc/275861
ER -

References

top
  1. [1] T. Kloks, D. Kratsch, and H. Muller, Asteroidal sets in graphs, Lecture Notes in Comput. Sci. 1335 (1997) 229-241. doi:10.1007/BFb0024501[Crossref] Zbl0897.05076
  2. [2] K. Cameron, C.T. Hóang and B. Lévêque, Asteroids in rooted and directed path graphs, Electron. Notes Discrete Math. 32 (2009) 67-74. doi:10.1016/j.endm.2009.02.010[Crossref] Zbl1267.05174
  3. [3] K. Cameron, C.T. Hóang and B. Lévêque, Characterizing directed path graphs by forbidden asteroids, J. Graph Theory 68 (2011) 103-112. doi:10.1002/jgt.20543[Crossref][WoS] Zbl1230.05139
  4. [4] S. Chaplick, M. Gutierrez, B.Lévêque and S.B.Tondato, From path graphs to di- rected path graphs, Lecture Notes in Comput. Sci. 6410 (2010) 256-265. doi:10.1007/978-3-642-16926-7 24[Crossref] Zbl1310.05196
  5. [5] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974) 47-56. doi:10.1016/0095-8956(74)90094-X[Crossref] 
  6. [6] C.G. Lekkerkerker and J.Ch. Boland, Representation of finite graph by a set of intervals on the real line, Fund. Math. (1962) 45-64. Zbl0105.17501
  7. [7] B.Lévêque, F. Maffray and M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, J. Graph Theory 62 (2009) 369-384. doi:10.1002/jgt.20407[Crossref] Zbl1221.05220
  8. [8] I. Lin, T. McKee and D.B. West, The leafage of a chordal graphs, Discuss. Math. Graph Theory 18 (1998) 23-48. doi:10.7151/dmgt.1061[Crossref] Zbl0912.05053
  9. [9] C. Monma and V. Wei, Intersection graphs of paths in a tree, J. Combin. Theory Ser. B 41 (1986) 141-181. doi:10.1016/0095-8956(86)90042-0[Crossref] 
  10. [10] B.S. Panda, The forbidden subgraph characterization of directed vertex graphs, Discrete Math. 196 (1999) 239-256. doi:10.1016/S0012-365X(98)00127-7[Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.