TAILIEUCHUNG - Báo cáo toán học: "Counting Connected Set Partitions of Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Counting Connected Set Partitions of Graphs. | Counting Connected Set Partitions of Graphs Frank Simon Peter Tittmannf and Martin Trinks Faculty Mathematics Sciences Computer Science University Mittweida Mittweida Germany Submitted Jun 14 2010 Accepted Jan 5 2011 Published Jan 12 2011 Mathematics Subject Classification 05C31 Abstract Let G V E be a simple undirected graph with n vertices then a set partition n V1 . Vk of the vertex set of G is a connected set partition if each subgraph G Vj induced by the blocks Vj of n is connected for 1 j k. Define qi G as the number of connected set partitions in G with i blocks. The partition polynomial is Q G x FXo qi G xi. This paper presents a splitting approach to the partition polynomial on a separating vertex set X in G and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial Q G x y Mn 2m 1 qij G xiyj is briefly discussed where qij G counts the number of connected set partitions with i blocks and j intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be P-hard. Keywords graph theory bond lattice chromatic polynomial splitting formula bounded treewidth yP-hard 1 Introduction One of the best-studied graph polynomials is the chromatic polynomial P G x giving the number of proper vertex colorings of an undirected graph G V E with at most x colors see . 2 8 9 12 11 . Rota 3 showed that the chromatic polynomial of a graph G is uniquely defined by its bond lattice nc G . The bond lattice can be defined as a sublattice of the partition lattice n V on V. A set partition n G n V belongs to nc G iff all blocks of n induce connected subgraphs of G. Email simon@ lEmail peter@ Email trinks@ THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P14 1 We investigate here the rank-generating function of nc G which we call the partition polynomial Q G x . There are two ways to consider Q G x namely from an order-theoretic point of view as rank-generating .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học