𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reductions of the Graph Reconstruction Conjecture

✍ Scribed by R. Statman

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
283 KB
Volume
36
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [l, p. 1 I]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall also show that the Graph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized "deck") of the graph.

πŸ“œ SIMILAR VOLUMES

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

On the critical graph conjecture
On the critical graph conjecture
✍ Hian Poh Yap πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 222 KB

## Abstract Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a __p__(β‰₯4)‐critical graph __K__ of odd order such that __K__ has a vertex __u__ of valency 2 and another vertex __v__ β‰  __u__ of valency ≀(__p__ + 2)/2, then ther

On the perfect graph conjecture
On the perfect graph conjecture
✍ H. Meyniel πŸ“‚ Article πŸ“… 1976 πŸ› Elsevier Science 🌐 English βš– 160 KB
The graph reconstruction number
The graph reconstruction number
✍ Frank Harary; Michael Plantholt πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

Dedicated ro the memory of Stan Ulam (31.