Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width. | Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width S. D. Noble Department of Mathematical Sciences Brunel University Kingston Lane Uxbridge UB8 3PH U.K. steven.noble@brunel.ac.uk Submitted Oct 30 2006 Accepted May 18 2009 Published May 29 2009 Mathematics Subject Classification 05C85 05C15 68R10 Abstract We show that for any k there is a polynomial time algorithm to evaluate the weighted graph polynomial U of any graph with tree-width at most k at any point. For a graph with n vertices the algorithm requires O akn2k 3 arithmetical operations where ak depends only on k. 1 Introduction Motivated by a series of papers 9 10 11 the weighted graph polynomial U was introduced in 22 . Chmutov Duzhin and Lando 9 10 11 introduce a graph polynomial derived from Vassiliev invariants of knots and note that this polynomial does not include the Tutte polynomial as a special case. With a slight generalisation of their definition we obtain the weighted graph polynomial U that does include the Tutte polynomial. The attraction of U is that it contains many other graph invariants as specialisations for instance the 2-polymatroid rank generating function of Oxley and Whittle 23 and as a consequence the matching polynomial the stable set polynomial 13 and the symmetric function generalisation of the chromatic polynomial 27 . Note however that there are non-isomorphic graphs with the same U polynomial. This is a corollary of a result of Sarmiento 26 showing that the coefficients of U and the polychromate determine one another. It remains an open problem to determine whether or not there are two nonisomorphic trees with the same U polynomial. We introduce U in Section 2 and review some of these results in more detail. The notion of tree-width was introduced by Robertson and Seymour as a key tool in their work on the graph minors project 24 25 . An equivalent notion studied extensively by Arnborg and Proskurowski see for instance 3 4 is that of a partial k-tree. THE .