✦ LIBER ✦

Claw-free graphs are edge reconstructible

✍ Scribed by M. N. Ellingham; L. Pyber; Xingxing Yu

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 318 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120317

No coin nor oath required. For personal study only.

✦ Synopsis

The Edge Reconstruction Conjecture states that all graphs with at least four edges are determined by their edge-deleted subgraphs. We prove that this is true for claw-free graphs, those graphs with no induced subgraph isomorphic to K,,3. This includes line graphs as a special case.

📜 SIMILAR VOLUMES

Claw-free 3-connected P11-free graphs ar

Claw-free 3-connected P11-free graphs are hamiltonian

✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T

9-Connected Claw-Free Graphs Are Hamilto

9-Connected Claw-Free Graphs Are Hamilton-Connected

✍ Stephan Brandt 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 130 KB

A graph is Hamilton-connected if any pair of vertices is joined by a hamiltonian path. In this note it is shown that 9-connected graphs which contain no induced claw K 1, 3 are Hamilton-connected, by reformulating and localizing a closure concept due to Ryja c ek, which turns claw-free graphs into l

Almost claw-free graphs

✍ Zdeněk Ryjáček 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

## Abstract We say that __G__ is almost claw‐free if the vertices that are centers of induced claws (__K__~1,3~) in __G__ are independent and their neighborhoods are 2‐dominated. Clearly, every claw‐free graph is almost claw‐free. It is shown that (i) every even connected almost claw‐free graph has

All 4-connected Line Graphs of Claw Free

All 4-connected Line Graphs of Claw Free Graphs Are Hamiltonian Connected

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Thomassen conjectured that every 4-connected line graph is hamiltonian. Here we shall see that 4-connected line graphs of claw free graphs are hamiltonian connected.

Claw-free circular-perfect graphs

✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that

Well-Covered Claw-Free Graphs

✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB