✦ LIBER ✦

Bidegreed graphs are edge reconstructible

✍ Scribed by W. J. Myrvold; M. N. Ellingham; D. G. Hoffman

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 829 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110304

No coin nor oath required. For personal study only.

✦ Synopsis

An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs is said to be edge reconstructible if there is no graph in the class w i t h four or more edges that is not edge reconstructible. This paper proves that bidegreed graphs (graphs whose vertices all have one of two possible degrees) are edge reconstructible. The results are then generalized to show that all graphs that do not have three consecutive integers in their degree sequence are also edge reconstructible.

📜 SIMILAR VOLUMES

Claw-free graphs are edge reconstructibl

Claw-free graphs are edge reconstructible

✍ M. N. Ellingham; L. Pyber; Xingxing Yu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 1 views

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.

Nearly acyclic graphs are reconstructibl

Nearly acyclic graphs are reconstructible

✍ Bennet Manvel; Joseph M. Weinstein 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 815 KB

## Abstract We prove that a graph __G__ is reconstructible if __G__ has a node __v__ with __G‐v__ acyclic. The proof uses colored graphs and shows how to reconstruct some graphs from pieces which share a common subgraph having few automorphisms.

Reconstructibility versus edge reconstru

Reconstructibility versus edge reconstructibility of infinite graphs

✍ Carsten Thomassen 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 151 KB

## RECONgTRUCTIBILITY VERSUI~ EDGE RECONSTR1UCTIBILtlY OF !NF![?CTE GN~APNS Cars,~en -FI-!Ob,~ ASSEN A.hah,,\*~atL~k /~.t;tir~\*., t h~ieersi;e~sp ~tk~'n, S0{P} Aarbus C. Detm~a& Rcc~ .d 23 [;cccm~cr 1~)77 [~¢ :{>.cd 7 April D)TS For every cm~dma! a >R o ~here exi::ts an ,:t-rQ,',ular .g;api~ w[?

The edge reconstruction of hamiltonian g

The edge reconstruction of hamiltonian graphs

✍ L. Pyber 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB 👁 1 views

## Abstract If a graph __G__ on __n__ vertices contains a Hamiltonian path, then __G__ is reconstructible from its edge‐deleted subgraphs for __n__ sufficiently large.

Edge-reconstruction of 4-connected plana

Edge-reconstruction of 4-connected planar graphs

✍ S. Fiorini; J. Lauri 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB 👁 2 views

## Abstract The object of this paper is to show that 4‐connected planar graphs are uniquely determined from their collection of edge‐deleted subgraphs.

The reconstruction conjecture is true if

The reconstruction conjecture is true if all 2-connected graphs are reconstructible

✍ Yang Yongzhi 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

It is shown that the Reconstruction Conjecture is true for all finite graphs if it is true for the 2-connected ones. We shall, for the most part, use the terminology of [2] and [ 4 ] . Graphs will be finite, simple, and undirected. Let G be a graph and u E V(G). Denote by d(u) the degree of u in G