Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Chromatically Unique Multibridge Graphs. | Chromatically Unique Multibridge Graphs . Dong Mathematics and Mathematics Education National Institute of Education Nanyang Technological University Singapore 637616 fmdong@ . Teo . Little M. Hendy Institute of Fundamental Sciences PN461 Massey University Palmerston North New Zealand . Koh Department of Mathematics National University of Singapore Singapore 117543 matkohkm@ Submitted Jul 28 2003 Accepted Dec 13 2003 Published Jan 23 2004 MR Subject Classification 05C15 Abstract Let 0 o1 a2 ak denote the graph obtained by connecting two distinct vertices with k independent paths of lengths a1 a2 ak respectively. Assume that 2 a1 a2 ak. We prove that the graph 0 a1 a2 ak is chromatically unique if ak a1 a2 and find examples showing that 0 a1 a2 ak may not be chromatically unique if ak a1 a2. Keywords Chromatic polynomials y-unique y-closed polygon-tree 1 Introduction All graphs considered here are simple graphs. For a graph G let V G E G v G e G g G P G A respectively be the vertex set edge set order size girth and chromatic polynomial of G. Two graphs G and H are chromatically equivalent or simply y-equivalent Corresponding author. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R12 1 symbolically denoted by G H if P G X P H X . Note that if H G then v H v G and e H e G . The chromatic equivalence class of G denoted by G is the set of graphs H such that H G. A graph G is chromatically unique or simply x-unique if G G . Whenever we talk about the chromaticity of a graph G we are referring to questions about the chromatic equivalence class of G. Let k be an integer with k 2 and let a1 a2 ak be positive integers with a aj 3 for all i j with 1 i j k. Let 0 a1 a2 ak denote the graph obtained by connecting two distinct vertices with k independent internally disjoint paths of lengths a1 a2 ak respectively. The graph Q a1 a2 ak is called a multibridge more specifically .
