Download PDF - The leafage of a chordal graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The leafage of a chordal graph

Authors 1, 2, 3

Affiliations

  1. National Ocean University
  2. Wright State University
  3. University of Illinois

Abstract

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal sets and structural properties of chordal graphs.

Keywords

ENG
chordal graph, subtree intersection representation, leafage

Bibliography

  1. H. Broersma, T. Kloks, D. Kratsch and H. Müller, Independent sets in asteroidal triple-free graphs, in: Proceedings of ICALP'97, P. Degano, R. Gorrieri, A. Marchetti-Spaccamela, (eds.), (Springer-Verlag, 1997), Lect. Notes Comp. Sci. 1256, 760-770.
  2. H. Broersma, T. Kloks, D. Kratsch and H. Müller, A generalization of AT-free graphs and a generic algorithm for solving triangulation problems, Memorandum No. 1385, University of Twente, Enschede, The Netherlands, 1997.
  3. P.A. Buneman, A characterization of rigid circuit graphs, Discrete Math. 9 (1974) 205-212, doi: 10.1016/0012-365X(74)90002-8.
  4. R.P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950) 161-166, doi: 10.2307/1969503.
  5. R.P. Dilworth, Some combinatorial problems on partially ordered sets, in: Combinatorial Analysis (Bellman and Hall, eds.) Proc. Symp. Appl. Math. (Amer. Math. Soc 1960), 85-90.
  6. G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776.
  7. D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pac. J. Math. 15 (1965) 835-855.
  8. F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory (B) 16 (1974) 47-56, doi: 10.1016/0095-8956(74)90094-X.
  9. F. Gavril, Generating the maximum spanning trees of a weighted graph, J. Algorithms 8 (1987) 592-597, doi: 10.1016/0196-6774(87)90053-8.
  10. P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964) 539-548, doi: 10.4153/CJM-1964-055-5.
  11. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980).
  12. T. Kloks, D. Kratsch and H. Müller, Asteroidal sets in graphs, in: Proceedings of WG'97, R. Möhring, (ed.), (Springer-Verlag, 1997) Lect. Notes Comp. Sci. 1335, 229-241.
  13. T. Kloks, D. Kratsch and H. Müller, On the structure of graphs with bounded asteroidal number, Forschungsergebnisse Math/Inf/97/22, FSU Jena, Germany, 1997.
  14. B. Leclerc, Arbres et dimension des ordres, Discrete Math. 14 (1976) 69-76, doi: 10.1016/0012-365X(76)90007-8.
  15. C.B. Lekkerkerker and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45-64.
  16. I.-J. Lin, M.K. Sen and D.B. West, Leafage of directed graphs, to appear.
  17. T.A. McKee, Subtree catch graphs, Congr. Numer. 90 (1992) 231-238.
  18. E. Prisner, Representing triangulated graphs in stars, Abh. Math. Sem. Univ. Hamburg 62 (1992) 29-41, doi: 10.1007/BF02941616.
  19. F.S. Roberts, Indifference graphs, in: Proof Techniques in Graph Theory (F. Harary, ed.), Academic Press (1969) 139-146.
  20. D.J. Rose, Triangulated graphs and the elimination process, J. Math. Ann. Appl. 32 (1970) 597-609, doi: 10.1016/0022-247X(70)90282-9.
  21. D.J. Rose, R.E. Tarjan and G.S. Leuker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comp. 5 (1976) 266-283, doi: 10.1137/0205021.
  22. Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428, doi: 10.1002/jgt.3190120313.
  23. J.R. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory 2 (1978) 265-267, doi: 10.1002/jgt.3190020311.
Discussiones Mathematicae Graph Theory
1998/18/1
Export to PBN, Opens in new tab
Pages:
23-48
Main language of publication
English
Received
1997-01-02
Accepted
1998-04-19
Published
1998
Exact and natural sciences