This HTML5 document contains 47 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n16https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Reconstruction_conjecture
dbo:wikiPageWikiLink
dbr:New_digraph_reconstruction_conjecture
Subject Item
dbr:New_digraph_reconstruction_conjecture
rdf:type
yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:Abstraction100002137 dbo:Disease yago:Speculation105891783 yago:PsychologicalFeature100023100 yago:Content105809192 yago:WikicatDirectedGraphs yago:WikicatConjectures yago:Concept105835747 yago:Idea105833840 yago:Hypothesis105888929 yago:Cognition100023271
rdfs:label
New digraph reconstruction conjecture
rdfs:comment
The reconstruction conjecture of Stanisław Ulam is one of the best-known open problems in graph theory. Using the terminology of Frank Harary it can be stated as follows: If G and H are two graphs on at least three vertices and ƒ is a bijection from V(G) to V(H) such that G\{v} and H\{ƒ(v)} are isomorphic for all vertices v in V(G), then G and H are isomorphic. If D and E are any two digraphs and ƒ is a bijection from V(D) to V(E) such that D\{v} and E\{ƒ(v)} are isomorphic and (od(v),id(v)) = (od(ƒ(v)),id(ƒ(v))) for all v in V(D), then D and E are isomorphic.
dcterms:subject
dbc:Unsolved_problems_in_graph_theory dbc:Conjectures dbc:Directed_graphs
dbo:wikiPageID
16130126
dbo:wikiPageRevisionID
1031078520
dbo:wikiPageWikiLink
dbc:Directed_graphs dbr:Outdegree dbr:Indegree dbr:Frank_Harary dbr:Stanisław_Ulam dbr:Directed_graph dbc:Conjectures dbc:Unsolved_problems_in_graph_theory dbr:Reconstruction_conjecture dbr:Graph_theory
owl:sameAs
wikidata:Q7016399 freebase:m.03y054x yago-res:New_digraph_reconstruction_conjecture n16:4smv8
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Unsolved
dbo:abstract
The reconstruction conjecture of Stanisław Ulam is one of the best-known open problems in graph theory. Using the terminology of Frank Harary it can be stated as follows: If G and H are two graphs on at least three vertices and ƒ is a bijection from V(G) to V(H) such that G\{v} and H\{ƒ(v)} are isomorphic for all vertices v in V(G), then G and H are isomorphic. In 1964 Harary extended the reconstruction conjecture to directed graphs on at least five vertices as the so-called digraph reconstruction conjecture. Many results supporting the digraph reconstruction conjecture appeared between 1964 and 1976. However, this conjecture was proved to be false when P. K. Stockmeyer discovered several infinite families of counterexample pairs of digraphs (including tournaments) of arbitrarily large order. The falsity of the digraph reconstruction conjecture caused doubt about the reconstruction conjecture itself. Stockmeyer even observed that “perhaps the considerable effort being spent in attempts to prove the (reconstruction) conjecture should be balanced by more serious attempts to construct counterexamples.” In 1979, Ramachandran revived the digraph reconstruction conjecture in a slightly weaker form called the new digraph reconstruction conjecture. In a digraph, the number of arcs incident from (respectively, to) a vertex v is called the outdegree (indegree) of v and is denoted by od(v) (respectively, id(v)). The new digraph conjecture may be stated as follows: If D and E are any two digraphs and ƒ is a bijection from V(D) to V(E) such that D\{v} and E\{ƒ(v)} are isomorphic and (od(v),id(v)) = (od(ƒ(v)),id(ƒ(v))) for all v in V(D), then D and E are isomorphic. The new digraph reconstruction conjecture reduces to the reconstruction conjecture in the undirected case, because if all the vertex-deleted subgraphs of two graphs are isomorphic, then the corresponding vertices must have the same degree. Thus, the new digraph reconstruction conjecture is stronger than the reconstruction conjecture, but weaker than the disproved digraph reconstruction conjecture. Several families of digraphs have been shown to satisfy the new digraph reconstruction conjecture and these include all the digraphs in the known counterexample pairs to the digraph reconstruction conjecture.
gold:hypernym
dbr:Problems
prov:wasDerivedFrom
wikipedia-en:New_digraph_reconstruction_conjecture?oldid=1031078520&ns=0
dbo:wikiPageLength
6402
foaf:isPrimaryTopicOf
wikipedia-en:New_digraph_reconstruction_conjecture
Subject Item
dbr:List_of_unsolved_problems_in_mathematics
dbo:wikiPageWikiLink
dbr:New_digraph_reconstruction_conjecture
Subject Item
dbr:New_Digraph_Reconstruction_Conjecture
dbo:wikiPageWikiLink
dbr:New_digraph_reconstruction_conjecture
dbo:wikiPageRedirects
dbr:New_digraph_reconstruction_conjecture
Subject Item
wikipedia-en:New_digraph_reconstruction_conjecture
foaf:primaryTopic
dbr:New_digraph_reconstruction_conjecture