Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Minimal Cycle Bases of Outerplanar Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Minimal Cycle Bases of Outerplanar Graphs. | Minimal Cycle Bases of Outerplanar Graphs Josef LEyDQLDa AND Peter F. Stadler6 c Dept. for Applied Statistics and Data Processing University of Economics and Business Administration Augasse 2-6 A-1090 Wien Austria Phone 43 1 31336-4695 Fax 43 1 31336-738 E-Mail Josef.Leydold@wu-wien.ac.at URL http statistik.wu-wien.ac.at staff leydold bInstitut fur Theoretische Chemie Universitat Wien Wahringerstrahe 17 A-1090 Wien Austria Phone 43 1 40480 665 Fax 43 1 40480-660 E-Mail studla@tbi.univie.ac.at Address for correspondence cThe Santa Fe Institute 1399 Hyde Park Road Santa Fe NM 87501 USA Phone 505 984 8800 Fax 505 982 0565 E-Mail stadler@santafe.edu URL http www.tbi.univie.ac.at studla Submitted July 18 1997 Accepted February 27 1998. Abstract 2-connected outerplanar graphs have a unique minimal cycle basis with length 2 EI V . They are the only Hamiltonian graphs with a cycle basis of this length. Keywords Minimal Cycle Basis Outerplanar Graphs AMS Subject Classification Primary 05C38. Secondary 92D20. 1 The electronic journal of combinatorics 5 1998 R16 2 1. Introduction The description of cyclic structures is an important problem in graph theory see e.g. 16 . Cycle bases of graphs have a variety of applications in science and engineering among them in structural analysis 11 and in chemical structure storage and retrieval systems 7 . Naturally minimal cycles bases are of particular practical interest. In this contribution we prove that outerplanar graphs have a unique minimal cycle basis. This result was motivated by the analysis of the structures of biopolymers. In addition we derive upper and lower bounds on the length of minimal cycle basis in 2-connected graphs. Biopolymers such as RNA DNA or proteins form well-dehned three dimensional structures. These are of utmost importance for their biological function. The most salient features of these structures are captured by their contact graph representing the set E of all pairs of monomers V that are spatially .