Complexity results in graph reconstruction |
| |
Authors: | Edith Hemaspaandra Lane A Hemaspaandra Stanis?aw P Radziszowski |
| |
Institution: | a Department of Computer Science, Rochester Institute of Technology, Rochester, NY 14623, USA b Department of Computer Science, University of Rochester, Rochester, NY 14627, USA |
| |
Abstract: | We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:- (1)
- , , , and .
- (2)
- For all k?2, and .
- (3)
- For all k?2, .
- (4)
- .
- (5)
- For all k?2, .
For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn∃(G) F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern∃(G) (see J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn∀(G) and ern∀(G), and give an example of a family {Gn}n?4 of graphs on n vertices for which vrn∃(Gn)<vrn∀(Gn). For every k?2 and n?1, we show that there exists a collection of k graphs on (2k-1+1)n+k vertices with 2n 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved. |
| |
Keywords: | Graph reconstruction Legitimate deck Graph isomorphism Reconstruction numbers |
本文献已被 ScienceDirect 等数据库收录! |
|