On Cayley’s formula for counting trees in nested interval graphs Academic Article uri icon


  • Abstract. In this paper it is shown that the spectrum of a nested interval graph has a very simple structure. From this result a formula is derived to the number of spanning trees in a nested interval graph; this is a generalization of the Cayley formula … Key words. Spectrum, Interval graph, Number of spanning trees, Cayley formula … 1 ,n n−1}. For more families of graphs … ∗Received by the editors 28 September 2004. Accepted for publication 24 October 2004. Handling Editor: Richard A. Brualdi. † IBM Research, TJ Watson Research Center, Yorktown Heights, NY 10598, USA (dcopper@us.ibm.com). ‡Max-Planck-Institut fur Informatik, Stuhlsatzenhausweg 85 66123 Saarbrucken, Germany (zvilo@eng.tau.ac.il). 241 … Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 11, pp. 241-245, November 2004 … Again we can extend the definition to equivalence classes …

publication date

  • January 1, 2004