TAILIEUCHUNG - Báo cáo toán học: "Uniquely Hamiltonian Characterizations of Distance-Hereditary and Parity Graphs"

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 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 Each component of G is built from a single .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã 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.