# Báo cáo toán học: "A note on circuit graphs Qing Cui"

## 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: A note on circuit graphs Qing Cui. | A note on circuit graphs Qing Cui Department of Mathematics Nanjing University of Aeronautics and Astronautics Nanjing 210016 P. R. China cui@ Submitted Oct 12 2009 Accepted Jan 22 2010 Published Jan 31 2010 Mathematics Subject Classifications 05C38 05C40 Abstract We give a short proof of Gao and Richter s theorem that every circuit graph contains a closed walk visiting each vertex once or twice. 1 Introduction We only consider finite graphs without loops or multiple edges. For a graph G we use V G and E G to denote the vertex set and edge set of G respectively. A k-walk in G is a walk passing through every vertex of G at least once and at most k times. A circuit graph G C is a 2-connected plane graph G with outer cycle C such that for each 2-cut S in G every component of G S contains a vertex of C. It is immediate that every 3-connected planar graph G is a circuit graph we may choose C to be any facial cycle of G . In 1994 Gao and Richter 3 proved that every circuit graph contains a closed 2-walk. The existence of such a walk in every 3-connected planar graph was conjectured by Jackson and Wormald 5 . Gao Richter and Yu 4 extended this result by showing that every 3-connected planar graph has a closed 2-walk such that any vertex visited twice is in a vertex cut of size 3. It is easy to see that this also implies Tutte s theorem 7 that every 4-connected planar graph is Hamiltonian. The main objective of this note is to present a short proof of Gao and Richter s result. Theorem 1 Let G C be a circuit graph and let u v G V C . Then there is a closed 2-walk W in G visiting u and v exactly once and traversing every edge of C exactly once. We conclude this section with some notation and terminology. A plane chain of blocks is a graph embedded in the plane with blocks B1 B2 . Bk such that for each i 1 . k 1 Bi and Bi l have a vertex in common no two of which are the same THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N10 1 and for each j 1 2 . k ui j Bị is in

TÀI LIỆU LIÊN QUAN
32    57    0
45    42    0
6    65    0
4    53    0
6    55    0
6    52    0
6    45    0
5    59    0
7    58    0
6    64    0
TÀI LIỆU XEM NHIỀU
13    32510    1652
3    19378    204
25    18683    3691
20    16774    1477
16    15868    2497
14    14343    2540
37    13059    2802
1    11365    401
3    10980    212
23    10568    384
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
67    166    1    07-07-2022
6    14    1    07-07-2022
6    17    1    07-07-2022
73    3    1    07-07-2022
236    81    2    07-07-2022
14    18    1    07-07-2022
5    2    1    07-07-2022
99    24    2    07-07-2022
13    36    1    07-07-2022
131    10    2    07-07-2022
144    92    1    07-07-2022
17    56    2    07-07-2022
18    2    1    07-07-2022
8    3    1    07-07-2022
10    12    1    07-07-2022
5    3    1    07-07-2022
115    22    1    07-07-2022
5    3    1    07-07-2022
207    18    1    07-07-2022
207    79    4    07-07-2022
TÀI LIỆU HOT
3    19378    204
13    32510    1652
3    1509    75
580    3634    346
62    4389    1
584    1964    81
171    3993    621
2    1751    72
51    2480    150
53    3346    175
Đã 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.