TAILIEUCHUNG - Báo cáo toán học: "Graph Powers and Graph Homomorphism"

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: Graph Powers and Graph Homomorphisms. | Graph Powers and Graph Homomorphisms Hossein Hajiabolhassan and Ali Taherkhani Department of Mathematical Sciences Shahid Beheshti University . Tehran Iran hhaj i@ a_taherkhani@ Submitted Sep 1 2008 Accepted Jan 13 2010 Published Jan 22 2010 Mathematics Subject Classifications 05C15 Abstract In this paper we investigate some basic properties of fractional powers. In this regard we show that for any non-bipartite graph G and positive rational numbers I I 2r 1 2r 1 . .2p 1 . 2r 1 2p i TTTp have G 2s 1 fZ 2q 1 ivpxt. WP the nnwpr õf G 2s I 1 2q I 1 we L-tave vjr eyr . livXj we sbumy bi-te power LiiAAUvOO or VJT 2 1 2r 1 that is the supremum of rational numbers 2r i such that G and G2s 1 have the same chromatic number. We prove that the power thickness of any non-complete circular complete graph is greater than one. This provides a sufficient condition for the equality of the chromatic number and the circular chromatic number of graphs. Finally we introduce an equivalent definition for the circular chromatic number of graphs in terms of fractional powers. Also we show that for any non-bipartite graph G if 0 2 1 3 X G -2 then x G2 1 3. Moreover x G Xc G if and only 2r 1 x G if there exists a rational number 2S 1 3 x G -2 for which x G2s 1 3. 1 Introduction Throughout this paper we only consider finite simple graphs unless otherwise stated. For a graph G let V G and E G denote its vertex and edge sets respectively. Denote two isomorphic graphs G and H by the symbol G H. Also a homomorphism from G to H is a map f V G V H such that adjacent vertices in G are mapped into adjacent vertices in H . uv G E G implies f u f v G E H . For simplicity the existence of a homomorphism is indicated by the symbol G H. Two graphs G and H are homomorphically equivalent denoted by G H if G H and H G. Also G H means that G H and there is no homomorphism from H to G. The symbol Hom G H is used to denote the set of all homomorphisms from G to H. In .

• 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