TAILIEUCHUNG - Báo cáo toán học: "Another characterisation of planar 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: Another characterisation of planar graphs. | Another characterisation of planar graphs C. H. C. Little Massey University Palmerston North New Zealand G. Sanjith Indian Institute of Technology Madras Chennai India theemergingmind@ Submitted Sep 13 2009 Accepted Mar 1 2010 Published Mar 8 2010 Mathematics Subject Classification 05C10 Abstract A new characterisation of planar graphs is presented. It concerns the structure of the cocycle space of a graph and is motivated by consideration of the dual of an elementary property enjoyed by sets of circuits in any graph. 1 Introduction Several characterisations of planar graphs are known. See 1-20 . We present a new one based on the structure of the cocycle space of a graph. Let G be a graph with vertex set VG and edge set EG. If S and T are disjoint sets of vertices we denote by S T the set of edges with one end in S and the other in T. For any S c VG we write S VG S and we define dS S S . This set is called a cocycle the cocycle determined by S or S . A bond is a minimal non-empty cocycle. Thus a non-empty cocycle dS in a connected graph G is a bond if and only if G S and G S are both connected. An isthmus is the unique member of a bond of cardinality 1. Let A and B be distinct bonds in G. We say that two distinct edges of B A are bound to each other by A with respect to B if they join vertices in the same two components of G A u B . Now let A1 A2 A3 B be distinct bonds in G and let a E B Al u A2 u A3 . For each i E 1 2 3 let Si be the set of edges bound to a by Ai with respect to B. We say that a is tied by A1 A2 A3 with respect to B if the following conditions hold Supported by KVPY THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N15 1 V ữ v4 Figure 1 K5 1. for each i there is a component of G Aị u B that contains an end of a and an end of an edge of Ai n B 2. each of S1 S2 S3 contains an edge that is in neither of the other two. Edge a is tied if there exist bonds A1 A2 A3 B such that a is tied by Al A2 A3 with respect to B . The

• 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