On some reconstruction problems about trees and disconnected graphs

Abstract

The Reconstruction Problem is considered to be one of the most important unsolved problems in Graph Theory. It was proposed by Kelly and Ulam in 1942 and who conjectured that any graph G on three or more vertices can be uniquely determined, up to isomorphism, from the collection of all unlabelled vertex-deleted subgraphs of G. Later in 1964, Harary formulated the related edge-reconstruction conjecture which states that any simple finite graph with at least four edges can be reconstructed from its edge-deleted subgraphs. Although both conjectures were proven to be true for several classes of graphs, the general problem remains unsolved. Thus graph theorists tried to study variants of this problem. One such variant was studied by Harary and Plantholt who came up with the idea of the reconstruction number - the minimum number of vertex-deleted subgraphs required in order to identify a graph up to isomorphism. The edge-reconstruction number of a graph is analogously defined. In this thesis we shall study edge-deleted subgraphs of trees and disconnected graphs as well as the smallest number of such subgraphs which will reconstruct those classes of graphs. We shall also study a very different type of reconstruction problem, namely when numbers of paths of a tree passing through any vertex (or edge) can determine the tree uniquely. The first chapter of this thesis deals with the basic notation and terminology that will be used throughout while Chapter 2 gives a general review of some important and well-known results in graph reconstruction. The main result of Chapter 3 is an improvement of Molina's result on the edge-reconstruction number of disconnected trees. He had shown that a disconnected graph whose components are not all isomorphic has edge-reconstruction number at most three. Moreover, he also showed that under certain conditions, including the property that at least one component has a cycle, the edge-reconstruction number is 2. In this chapter we give an alternative proof of Molina's result and then characterise those disconnected graphs which have the largest possible edge-reconstruction number. We also investigate those properties for which a forest would have an edge-reconstruction number of 2. From some empirical evidence provided by Rivshin and the results obtained in Chapter 3, we conjecture that if G is a disconnected graph whose components are all isomorphic to H and has reconstruction number more than 3, then the component H is isomorphic to a star. In Chapter 4, we build on Molina's work on trees. He stated that for a unicentroidal tree with at least four edges, its edge-reconstruction number is at most three. But if T is a bicentroidal tree then, Molina's result says that, it can be sometimes two or at most three. Molina's result does not indicate when a bicentroidal tree has an edge-reconstruction number of 2 or 3. We show that, apart from three known exceptions, all bicentroidal trees have edge-reconstruction number equal to 2. Using results from computer searches made by Rivshin and more recently by Myrvold, we also exhibit the known unicentroidal trees having edgereconstruction number equal to 3 and we conjecture that the three infinite families of unicentroidal trees which we have found to have edge-reconstruction number equal to 3, are the only ones. Chapter 5 deals with the degree-associated edge-reconstruction number - an area in reconstruction which has recently progressed quite rapidly. This is a weakened version of the original Reconstruction Problem since we are given the degree of the deleted edge along with each deleted edge-card. The degree-associated edge-reconstruction number of a graph G, denoted by dern(G), is the minimum number of degree-associated edge-cards called da-ecards, that suffice to determine the graph G. We investigate how the degree-associated edge-reconstruction number of disconnected graphs and trees changes when compared to their respective edge-reconstruction numbers which are studied in Chapters 3 and 4. In particular we prove that dern of a caterpillar is at most two and finally we even conjecture that for any tree T, dern(T) is at most two. In Chapter 6 we review some work done by Dulio and Pannone on the vertex path-table of a tree and we introduce the edge path-table which consists of an (n􀀀1) d matrix, where n = jV (G)j and d is the diameter of the tree, and whose (i; j)th entry gives the number of paths of length j passing through edge ei. We show that in general, all path-tables of a tree T which have been proposed do not determine T uniquely. We shall show that in trees, the number of paths passing through the edge xy can only be expressed in terms of paths passing through vertices x and y up to a length of 4. Also, in contrast with the results obtained by Dulio and Pannone on the vertex path-table, we show that the row of the edge path-table that represents the central edge of a tree T of odd diameter, is unique in the edge path-table. Finally we show that caterpillars and a special kind of tree which we shall call Restricted Thin Trees (RTT) can be reconstructed from their path-tables. The work in Chapters 3 and 4 have been published in [6] and [7] respectively, while Chapters 5 and 6 have been submitted for publication and they correspond to [3] and [2].