MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Lotker, Zvi
Majumdar, Debapriyo
Narayanaswamy, N.S.
Weber, Ingmar		dblp
dblp
dblp
dblp
Not MPG Author(s):
Lotker, Zvi
Narayanaswamy, N.S.
Editor(s):
Chen, Danny Z.
Lee, D. T.		dblp
dblp
Not MPII Editor(s):
Chen, Danny Z.
Lee, D. T.
BibTeX cite key*:
lotkeretal06cocoon
Title, Booktitle
Title*:
Sequences Characterizing k-Trees
Booktitle*:
Computing and Combinatorics, 12th Annual International Conference, COCOON 2006
Event, URLs
Conference URL::
http://www.iis.sinica.edu.tw/cocoon06/
Downloading URL:
http://www.springerlink.com/content/v2375455r316v272/fulltext.pdf
Event Address*:
Taipei, Taiwan
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
9 June 2006
Event End Date:
9 June 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4112
Number:
Month:
Pages:
216-225
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
3-540-36925-2
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:

A non-decreasing sequence of n integers is the degree sequence of a 1-tree (i.e., an ordinary tree) on n vertices if and only if there are least two 1’s in the sequence, and the sum of the elements is 2(n–1). We generalize this result in the following ways. First, a natural generalization of this statement is a necessary condition for k-trees, and we show that it is not sufficient for any k > 1. Second, we identify non-trivial sufficient conditions for the degree sequences of 2-trees. We also show that these sufficient conditions are almost necessary using bounds on the partition function p(n) and probabilistic methods. Third, we generalize the characterization of degrees of 1-trees in an elegant and counter-intuitive way to yield integer sequences that characterize k-trees, for all k.
URL for the Abstract:
http://www.springerlink.com/content/v2375455r316v272/
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{lotkeretal06cocoon,
AUTHOR = {Lotker, Zvi and Majumdar, Debapriyo and Narayanaswamy, N.S. and Weber, Ingmar},
 EDITOR = {Chen, Danny Z. and Lee, D. T.},
 TITLE = {Sequences Characterizing k-Trees},
 BOOKTITLE = {Computing and Combinatorics, 12th Annual International Conference, COCOON 2006},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4112},
 PAGES = {216--225},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Taipei, Taiwan},
 ISBN = {3-540-36925-2},
}

Entry last modified by Christine Kiesel, 02/07/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ingmar Weber		Created
06/09/2006 12:16:11
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Ingmar Weber
Ingmar Weber

Edit Dates
07.02.2007 17:52:52
09/18/2006 11:17:43 AM
06/09/2006 12:16:11 PM