Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam. Given a graph , a vertex-deleted subgraph of is a subgraph formed by deleting exactly one vertex from . By definition, it is an induced subgraph of . For a graph , the deck of G, denoted , is the multiset of isomorphism classes of all vertex-deleted subgraphs of . Each graph in is called a card. Two graphs that have the same deck are said to be hypomorphic. With these definitions, the conjecture can be stated as: Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic. (The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.) Harary suggested a stronger version of the conjecture: Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic. Given a graph , an edge-deleted subgraph of is a subgraph formed by deleting exactly one edge from . For a graph , the edge-deck of G, denoted , is the multiset of all isomorphism classes of edge-deleted subgraphs of . Each graph in is called an edge-card. Edge Reconstruction Conjecture: (Harary, 1964) Any two graphs with at least four edges and having the same edge-decks are isomorphic. In context of the reconstruction conjecture, a graph property is called recognizable if one can determine the property from the deck of a graph. The following properties of graphs are recognizable: Order of the graph – The order of a graph , is recognizable from as the multiset contains each subgraph of created by deleting one vertex of . Hence Number of edges of the graph – The number of edges in a graph with vertices, is recognizable. First note that each edge of occurs in members of . This is true by the definition of which ensures that each edge is included every time that each of the vertices it is incident with is included in a member of , so an edge will occur in every member of except for the two in which its endpoints are deleted.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.