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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.