PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 4 | 603-614
Tytuł artykułu

Asteroidal Quadruples in non Rooted Path Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
35
Numer
4
Strony
603-614
Opis fizyczny
Daty
wydano
2015-11-01
otrzymano
2014-05-15
poprawiono
2014-12-16
zaakceptowano
2014-12-16
online
2015-11-10
Twórcy
  • Conicet Dto. de Matemática Facultad de Ciencias Exactas Universidad Nacional de La Plata Argentina, marisa@mate.unlp.edu.ar
Bibliografia
  • [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]
  • [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]
  • [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]
  • [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]
  • [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] 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.
  • [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]
  • [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]
  • [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] 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1821
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.