Bidegreed graphs are edge reconstructible. (English) Zbl 0661.05047
An edge-deleted subgraph of a graph is a subgraph obtained by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is edge reconstructible, that is, is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. This paper proves that all bidegreed graphs (those with vertices of just two different degrees) with four or more edges are edge reconstructible. The paper includes details of earlier papers on the subject, drawing attention to an error in one of them.
Reviewer: C.R.J.Clapham
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
References:
| [1] | The reconstruction of graphs. Preprint, University of Waterloo (1983). |
| [2] | Bondy, J. Graph Theory 1 pp 227– (1977) |
| [3] | and , Edge-Reconstruction of Bidegree Graphs. Report for graduate course, Dept of Combinatorics and Optimization, University of Waterloo (April 1984). |
| [4] | On the reconstruction of a graph from a collection of subgraphs. Theory of Graphs and its Applications, Proceedings of the Symposium held in Prague, 1964. Ed. Czechoslovak Academy of Sciences, Prague (1964) 47–52, reprinted, Academic Press, New York (1964). |
| [5] | On the Reconstruction Problem in Graph Theory. Ph.D. thesis, California Institute of Technology, Pasadena (1981). |
| [6] | letter to J. A. Bondy (March 1984). |
| [7] | The edge reconstructibility of bi-degreed graphs. University of Waterloo Research Report CORR 78-74 (1978). |
| [8] | Swart, Ann. Discrete Math. 9 pp 7– (1980) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
