# 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

TÀI LIỆU LIÊN QUAN
32    85    0
45    80    0
6    107    0
4    73    0
6    90    0
6    94    0
6    80    0
5    83    0
7    99    0
6    104    0
TÀI LIỆU XEM NHIỀU
13    41235    2421
3    25182    250
25    24859    4300
16    20339    2847
20    19744    1550
14    19662    2977
1    19557    621
37    16430    2960
3    16389    331
1    14957    135
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
9    604    1    13-07-2024
215    107    7    13-07-2024
114    85    1    13-07-2024
5    337    1    13-07-2024
6    93    1    13-07-2024
5    354    7    13-07-2024
7    95    2    13-07-2024
8    453    1    13-07-2024
42    404    9    13-07-2024
3    86    1    13-07-2024
12    85    1    13-07-2024
33    369    5    13-07-2024
75    393    6    13-07-2024
15    259    1    13-07-2024
4    168    2    13-07-2024
8    204    2    13-07-2024
32    524    5    13-07-2024
132    148    1    13-07-2024
4    124    1    13-07-2024
4    62    1    13-07-2024
TÀI LIỆU HOT
3    25182    250
13    41235    2421
3    3015    81
580    5336    363
584    3571    101
62    6925    1
171    5940    721
2    3388    78
51    4693    200
53    4991    189
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.