Extended star graphs

Marisa Gutierrez, Silvia Beatriz Tondato

Abstract


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


clique trees, asteroids, extended star graphs

Full Text:

PDF

References


M. Habib, J. Stacho, Polynomial-time algorithm for the

leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757, 2009, 290--300.

C.G. Lekkerkerker, J. Ch. Boland, Representation of finite graph by a set of intervals on the real line, Fundamenta Mathematicae Li, 1962, 45--64.

B. Lévêque, F. Maffray, M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, Journal of Graph Theory 62, 2009, 369--384.

I. Lin, T. McKee and D. B. West, The leafage of a chordal graphs, Discussiones Mathematicae Graph Theory 18, 1998, 23--48.

C. Monma, V. Wei, Intersection graphs of paths in a tree, J. Combin. Theory B 41, 1986, 141--181.

B.S. Panda, The forbidden subgraph characterization of directed vertex graphs, Discrete Mathematics 196, 1999, 239--256.


Refbacks

  • There are currently no refbacks.