Originators: M. Yancey (presented by D. McDonald - REGS 2010)
Definitions: Let G be a multigraph. The (edge) deck of G is the multiset {G-e: e∈E(G)}; the members of the deck are cards. A multigraph G is edge-reconstructible if every multigraph with the same deck as G is isomorphic to G. Likewise, a multigraph property (or parameter) is edge-reconstructible if its occurrence (or value) for a particular multigraph can be determined from the deck. A class of multigraphs is edge-recognizable if the property of membership in that class is edge-reconstructible. A multigraph is simple if it has no loops or multi-edges.
Background: The Edge-Reconstruction Conjecture states that every simple graph with more than three edges is edge-reconstructible. The Edge-Reconstruction Conjecture is easier than the Reconstruction Conjecture, which asserts that every simple graph with more than two vertices is reconstructible from its deck of vertex-deleted subgraphs (cards are obtained by removing vertices rather than edges). The Reconstruction Conjecture implies the Edge-Reconstruction Conjecture. A survey of results on edge-reconstruction appears in [MRV]. Surveys on the original vertex analogue appear in [B,BH,L].
Conjecture 1: Every nonsimple multigraph with more than two edges is edge-reconstructible.
Comments: Multigraphs in which every multiedge has the same multiplicity m have the same vertex-deleted subgraphs as their underlying simple graphs, except each edge is replaced by a multiedge of multiplicity m, so the Reconstruction Conjecture on nonsimple multigraphs is more difficult than the Reconstruction Conjecture on simple graphs. However, the Edge-Reconstruction Conjecture may be easier for nonsimple multigraphs than for simple graphs.
In particular, with more than two edges, a multigraph is nonsimple if and only if it has a nonsimple card, so the desired class is edge-recognizable. Multigraphs with more than two edges and no edges of multiplicity 1 are edge-reconstructible; some card will have exactly one edge with the smallest multiplicity, and the multigraph is reconstructed by adding another copy of that edge.
For Q with fewer edges than G, the number of times Q appears as a subgraph of G and the number of times it appears as an induced subgraph of G are edge-reconstructible. Another edge-reconstructible parameter on these multigraphs is the multiset consisting of, for each vertex v of G, the multiset of multiplicities of edges incident to v.
Problem 2: Show that certain classes of nonsimple multigraphs (perhaps disconnected multigraphs with more than one nontrivial component, or multigraphs whose underlying simple graphs are trees) are edge-reconstructible.
References:
[B] J. A. Bondy, A graph reconstructor's manual, in Surveys in Combinatorics
(Guildford, 1991), Lond. Math. Soc. Lec. Notes 166 (Cambridge U. Press,
1991), 221--252.
[BH] J. A. Bondy and R. L. Hemminger, Graph
reconstruction---a survey, J. Graph Theory 1 (1977), 227--268.
[L] J. Lauri, Pseudosimilarity in graphs---a survey, Ars Combin. 46 (1997),
77--95.
[MRV] Maccari, Alicia; Rueda, Olga; Viazzi, Vilma; A survey on edge
reconstruction of graphs. J. Discrete Math. Sci. Cryptography 5 (2002),
1--11.