Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Uniquely Hamiltonian Characterizations of Distance-Hereditary and Parity Graphs. | Uniquely Hamiltonian Characterizations of Distance-Hereditary and Parity Graphs Terry A. McKee Department of Mathematics Statistics Wright State University Dayton Ohio 45435 USA terry.mckee@wright.edu Submitted Apr 9 2007 Accepted Sep 19 2008 Published Sep 29 2008 Mathematics Subject ClassiEcations 05C75 05C45 Abstract A graph is shown to be distance-hereditary if and only if no induced subgraph of order Eve or more has a unique hamiltonian cycle this is also equivalent to every induced subgraph of order Eve or more having an even number of hamiltonian cycles. Restricting the induced subgraphs to those of odd order Eve or more gives two similar characterizations of parity graphs. The close relationship between distance-hereditary and parity graphs is unsurprising but their connection with hamiltonian cycles of induced subgraphs is unexpected. 1 Distance-hereditary graphs Howorka 10 defined a graph to be a distance-hereditary graph if the distance between vertices in connected induced subgraphs always equals the distance between them in the full graph. This is equivalent to every cycle of length five or more having two crossed chords 1 4 7 9 contain many additional characterizations. Lemma 1 will state two characterizations of distance-hereditary graphs from 1 that will be used below. As in 4 the vertices in a set S c V G are twins if they all have exactly the same neighbors in G S and are either pairwise adjacent in which case they are true twins or pairwise nonadjacent in which case they are false twins . A pendant vertex is a vertex v for which there is a vertex w such that N v w the edge vw is then a pendant edge. A graph G0 is a one-vertex expansion 1 of a graph G if V G0 V G u v0 V G where either v0 has a twin vertex v in G or v0 is a pendant vertex of G0. Lemma 1 Bandelt Muller 1986 Each of the following is equivalent to G being a distance-hereditary graph THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N36 1 1.1 Each component of G is built from a single .