Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: On the total weight of weighted matchings of segment graphs. | On the total weight of weighted matchings of segment graphs Thomas Stoll School of Computer Science University of Waterloo Waterloo ON Canada N2L3G1 tstoll@cs.uwaterloo.ca Jiang Zeng Institute Camille Jordan Universite Claude-Bernard Lyon I 69622 Villeurbanne France zeng@math.univ-lyon1.fr Submitted Apr 30 2008 Accepted Apr 24 2009 Published Apr 30 2009 Mathematics Subject Classification 11D45 05A15 33C45 Abstract We study the total weight of weighted matchings in segment graphs which is related to a question concerning generalized Chebyshev polynomials introduced by Vauchassade de Chaumont and Viennot and more recently investigated by Kim and Zeng. We prove that weighted matchings with sufficiently large node-weight cannot have equal total weight. 1 Introduction Let Segn V E be the graph i.e. the segment graph with vertex set V n and E the set of undirected edges i i 1 with 1 i n 1. A matching p of Segn is a subset of edges with no two edges being connected by a common vertex. A node in Segn is called isolated with respect to a given matching if it is not contained in the matching. Given a matching we put the weight x on each isolated vertex and the weight 1 or a on each edge i i 1 depending on whether i is odd or even. Denote by M Segn the set of all matchings of Segn. The weighted matching polynomial is then given by Un x a 22 1 1 1 aEINDMxra-2 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R56 1 x x x x x x x x x x x -1 1 1 a x x x x x x x x x a x x 1 x x x a 1 1 1 1 x 1 a x 9 a a x Figure 1 Weighted matchings of Seg4 and Seg5. where ụ denotes the number of edges of ụ and EIND ụ the number of edges i i 1 with i even. The polynomials Un x a came first up in some enumeration problems in molecular biology 15 and are generalized Chebyshev polynomials of the second kind because we get the classical monic Chebyshev polynomials of the second kind 14 p. 29 for a 1. Recently Kim and Zeng 7 used 1 and a combinatorial interpretation of the corresponding moments to .
