On Models of Directed Path Graphs Non Rooted Directed Path Graphs

详细信息    查看全文

• 作者：Marisa Gutierrez ; Silvia B. Tondato
• 关键词：Clique trees ; Rooted directed path graphs ; Asteroidal quadruples
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：32
• 期：2
• 页码：663-684
• 全文大小：698 KB
• 参考文献：1.Cameron, K., Hoáng, C.T., Lévêque, B.: Asteroids in rooted and directed path graphs. Electron. Notes Discrete Math. 32, 67–74 (2009)CrossRef
  2.Cameron, K., Hoáng, C.T., Lévêque, B.: Characterizing directed path graphs by forbidden asteroids. J. Graph Theory 68, 103–112 (2011)CrossRef MathSciNet MATH
  3.Chaplick, S., Stacho, J.: The vertex leafage of chordal graphs. Discrete Appl. Math. 168, 14–25 (2014)CrossRef MathSciNet MATH
  4.Chaplick, S., Gutierrez, M., Lévêque, B., Tondato, S.B.: From path graphs to directed path graphs, WG’10. Lecture Notes Comput. Sci. 6410, 256–265 (2010)CrossRef
  5.Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory B 16, 47–56 (1974)CrossRef MathSciNet MATH
  6.Gutierrez, M., Lévêque, B., Tondato, S.B.: Asteroidal quadruples in non rooted path graphs. Discussiones Mathematicae Graph Theory (2014, accepted)
  7.Gutierrez, M., Tondato, S.B.: On path models of path graphs (2011)
  8.Lekkerkerker, C.G., Boland, J.Ch.: Representation of finite graph by a set of intervals on the real line. Fundam. Math. Li, 45–64 (1962)
  9.Lévêque, B., Maffray, F., Preissmann, M.: Characterizing path graphs by forbidden induced subgraphs. J. Graph Theory 62, 369–384 (2009)CrossRef MathSciNet MATH
  10.Lin, I., McKee, T., West, D.B.: The leafage of a chordal graphs. Discuss. Math. Graph Theory 18, 23–48 (1998)CrossRef MathSciNet
  11.Monma, C., Wei, V.: Intersection graphs of paths in a tree. J. Combin. Theory B 41, 141–181 (1986)CrossRef MathSciNet MATH
  12.Panda, B.S.: The forbidden subgraph characterization of directed vertex graphs. Discrete Math. 196, 239–256 (1999)CrossRef MathSciNet MATH
  
• 作者单位：Marisa Gutierrez (1) (2)
  Silvia B. Tondato (2)
  
  1. Conicet, Facultad de Ciencias Exactas, Universidad Nacional de La Plata, Calle 50 y 115, 1900, La Plata, Argentina
  2. Departamento de Matemática, Facultad de Ciencias Exactas, Universidad Nacional de La Plata, Calle 50 y 115, 1900, La Plata, Argentina
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed 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 directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.