The leafage of a chordal graph

In-Jen Lin; Terry A. McKee; Douglas B. West

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 1, page 23-48
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

In-Jen Lin, Terry A. McKee, and Douglas B. West. "The leafage of a chordal graph." Discussiones Mathematicae Graph Theory 18.1 (1998): 23-48. <http://eudml.org/doc/270535>.

@article{In1998,
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.},
author = {In-Jen Lin, Terry A. McKee, Douglas B. West},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chordal graph; subtree intersection representation; leafage; asteroidal set},
language = {eng},
number = {1},
pages = {23-48},
title = {The leafage of a chordal graph},
url = {http://eudml.org/doc/270535},
volume = {18},
year = {1998},
}

TY - JOUR
AU - In-Jen Lin
AU - Terry A. McKee
AU - Douglas B. West
TI - The leafage of a chordal graph
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 1
SP - 23
EP - 48
AB - 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.
LA - eng
KW - chordal graph; subtree intersection representation; leafage; asteroidal set
UR - http://eudml.org/doc/270535
ER -

References

top
  1. [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. Zbl0918.68072
  2. [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. Zbl1009.68099
  3. [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. [4] R.P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950) 161-166, doi: 10.2307/1969503. Zbl0038.02003
  5. [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. Zbl0096.00601
  6. [6] G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. Zbl0098.14703
  7. [7] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pac. J. Math. 15 (1965) 835-855. Zbl0132.21001
  8. [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. Zbl0266.05101
  9. [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. Zbl0636.68091
  10. [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. Zbl0121.26003
  11. [11] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980). 
  12. [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. Zbl0897.05076
  13. [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. Zbl0989.05059
  14. [14] B. Leclerc, Arbres et dimension des ordres, Discrete Math. 14 (1976) 69-76, doi: 10.1016/0012-365X(76)90007-8. Zbl0318.06001
  15. [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. Zbl0105.17501
  16. [16] I.-J. Lin, M.K. Sen and D.B. West, Leafage of directed graphs, to appear. 
  17. [17] T.A. McKee, Subtree catch graphs, Congr. Numer. 90 (1992) 231-238. Zbl0791.05022
  18. [18] E. Prisner, Representing triangulated graphs in stars, Abh. Math. Sem. Univ. Hamburg 62 (1992) 29-41, doi: 10.1007/BF02941616. Zbl0779.05039
  19. [19] F.S. Roberts, Indifference graphs, in: Proof Techniques in Graph Theory (F. Harary, ed.), Academic Press (1969) 139-146. 
  20. [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. Zbl0216.02602
  21. [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. Zbl0353.65019
  22. [22] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428, doi: 10.1002/jgt.3190120313. Zbl0654.05022
  23. [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. Zbl0441.05022

NotesEmbed ?

top

You must be logged in to post comments.