Geodesic
Extended star graphs
Algebra and discrete mathematics, Tome 21 (2016) no. 2, pp. 239-254.

Voir la notice de l'article provenant de la source Math-Net.Ru

Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. An extended star graph is the intersection graph of a family of subtrees of a tree that has exactly one vertex of degree at least three. An asteroidal triple in a graph 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. Several subclasses of chordal graphs (interval graphs, directed path graphs) have been characterized by forbidden asteroids. In this paper, we define, a subclass of chordal graphs, called extended star graphs, prove a characterization of this class by forbidden asteroids and show open problems.
Keywords: asteroids, extended star graphs.
Mots-clés : clique trees 
@article{ADM_2016_21_2_a5,
     author = {Marisa Gutierrez and Silvia Beatriz Tondato},
     title = {Extended star graphs},
     journal = {Algebra and discrete mathematics},
     pages = {239--254},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2016_21_2_a5/}
}
TY  - JOUR
AU  - Marisa Gutierrez
AU  - Silvia Beatriz Tondato
TI  - Extended star graphs
JO  - Algebra and discrete mathematics
PY  - 2016
SP  - 239
EP  - 254
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2016_21_2_a5/
LA  - en
ID  - ADM_2016_21_2_a5
ER  - 
%0 Journal Article
%A Marisa Gutierrez
%A Silvia Beatriz Tondato
%T Extended star graphs
%J Algebra and discrete mathematics
%D 2016
%P 239-254
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2016_21_2_a5/
%G en
%F ADM_2016_21_2_a5
Marisa Gutierrez; Silvia Beatriz Tondato. Extended star graphs. Algebra and discrete mathematics, Tome 21 (2016) no. 2, pp. 239-254. http://geodesic.mathdoc.fr/item/ADM_2016_21_2_a5/

[1] J. R. S. Blairk, B. W. Peyton, “On finding minimum-diameter clique trees”, Nordic Journal of Computing, 1 (1994), 173–201 | MR

[2] K. Cameron, C. T. Hoáng, B. Lévêque, “Asteroids in rooted and directed path graphs”, Electronic Notes in Discrete Mathematics, 32 (2009), 67–-74 | DOI | MR | Zbl

[3] K. Cameron, C. T. Hoáng, B. Lévêque, “Characterizing directed path graphs by forbidden asteroids”, Journal of Graph Theory, 68 (2011), 103–112 | DOI | MR | Zbl

[4] S. Chaplick, J. Stacho, “The vertex leafage of chordal graphs”, Discrete Applied Mathematics, 168 (2014), 14–25 | DOI | MR | Zbl

[5] S. Chaplick, M. Gutierrez, B. Lévêque, S. B. Tondato, “From path graphs to directed path graphs” (WG'10), Lecture Notes in Computer Science, 6410 (2010), 256–265 | DOI | MR | Zbl

[6] F. Gavril, “The intersection graphs of subtrees in trees are exactly the chordal graphs”, J. Combin. Theory B, 16 (1974), 47–56 | DOI | MR | Zbl

[7] M. Gutierrez, J. L. Szwarcfiter, S. B. Tondato, “Clique trees of chordal graphs: leafage and 3-asteroidals”, Electronic Notes in Discrete Mathematics, 30 (2008), 237–242 | DOI | MR | Zbl

[8] M. Gutierrez, S. B. Tondato, “Special asteroidal quadruple on directed path graph non rooted path graph”, Electronic Notes in Discrete Mathematics, 44 (2013), 47–52 | DOI

[9] M. Gutierrez, S. B. Tondato, “On models of directed path graphs non rooted directed path graphs”, Graphs and Combinatorics, In press | MR

[10] M. Gutierrez, S. B. Tondato, Forbidden subgraph characterization of extended star directed path graphs that are not rooted directed path graphs, Submitted, 2015 | MR

[11] M. Habib, J. Stacho, “Polynomial-time algorithm for the leafage of chordal graphs”, Algorithms — ESA 2009, Lecture Notes in Computer Science, 5757, 2009, 290–300 | DOI | MR | Zbl

[12] C. G. Lekkerkerker, J. Ch. Boland, “Representation of finite graph by a set of intervals on the real line”, Fundamenta Mathematicae, 51 (1962), 45–64 | MR | Zbl

[13] B. Lévêque, F. Maffray, M. Preissmann, “Characterizing path graphs by forbidden induced subgraphs”, Journal of Graph Theory, 62 (2009), 369–384 | DOI | MR | Zbl

[14] I. Lin, T. McKee and D. B. West, “The leafage of a chordal graphs”, Discussiones Mathematicae Graph Theory, 18 (1998), 23–48 | DOI | MR | Zbl

[15] C. Monma, V. Wei, “Intersection graphs of paths in a tree”, J. Combin. Theory B, 41 (1986), 141–181 | DOI | MR | Zbl

[16] B. S. Panda, “The forbidden subgraph characterization of directed vertex graphs”, Discrete Mathematics, 196 (1999), 239–256 | DOI | MR | Zbl