Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/111347
Title: | On disconnected graph with large reconstruction number |
Authors: | Asciak, Kevin J. Lauri, Josef |
Keywords: | Graph theory Mathematics Graphic methods Mathematics—Charts, diagrams, etc. |
Issue Date: | 2002 |
Publisher: | Centre for Discrete Mathematics & Computing |
Citation: | Asciak, K. J., & Lauri, J. (2002). On disconnected graph with large reconstruction number. Ars Combinatoria, 62, 173-182. |
Abstract: | The reconstruction number rn(G) of graph G is the minimum number of vertex-deleted subgraphs of G required in order to identify G up to isomporphism. Myrvold and Molina have shown that if G is disconnected and not all components are isomorphic then rn(G) = 3, whereas, if all components are isomorphic and have c vertices each, then rn(G) can be as large as c + 2. In this paper we propose and initiate the study of the gap between rn(G) = 3 and rn(G) = c + 2. Myrvold showed that if G consists of p copies of K" then rn(G) = c + 2. We show that, in fact, this is the only class of disconnected graphs with this value of rn(G). We also show that if rn(G) > c + 1 (where c is still the number of vertices in any component), then, again, G can only be copies of Kc. It then follows that there exist no disconnected graphs G with c vertices in each component and rn( G) = c + 1. This poses the problem of obtaining for a given c, the largest value of/ = t(c) such that there exists a disconnected graph with all components of order c, isomorphic and not equal to Kc and is snch that rn(G) = t. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/111347 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
On_disconnected_graph_with_large_reconstruction_number_2002.pdf Restricted Access | 164.7 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.