**ID:**14362 |

**Type of Publication:** Conference Proceedings |

**Authors:** Zvi Lotker, D.Majumdar, N.S.Narayanaswamy, I.Weber |

**Title:** Sequences characterizing k-Trees |

**ConferenceName:** Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

**Publication:** Computing and Combinatorics. 12th Annual International Conference, COCOON 2006. Proceedings (Lecture Notes in Computer Science Vol.4112) |

**Year:** 2006 |

**Volume:** 4112 NCS |

**Pages:** 216 - 225 |

**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. © Springer-Verlag Berlin Heidelberg 2006. |

**Keywords:** Boolean functions;Computational geometry;Probabilistic logics;Functions;Data processing;Computational methods; , |

**Last Updated:** 9/4/2007 12:00:00 AM |