Matches in DBpedia 2014 for { <http://dbpedia.org/resource/New_digraph_reconstruction_conjecture> ?p ?o. }
Showing items 1 to 27 of
27
with 100 items per page.
- New_digraph_reconstruction_conjecture abstract "The reconstruction conjecture of Stanislaw 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)).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 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. As of 2014, no counterexample to the new digraph reconstruction conjecture is known.".
- New_digraph_reconstruction_conjecture wikiPageID "16130126".
- New_digraph_reconstruction_conjecture wikiPageRevisionID "604315961".
- New_digraph_reconstruction_conjecture hasPhotoCollection New_digraph_reconstruction_conjecture.
- New_digraph_reconstruction_conjecture subject Category:Conjectures.
- New_digraph_reconstruction_conjecture subject Category:Directed_graphs.
- New_digraph_reconstruction_conjecture type Abstraction100002137.
- New_digraph_reconstruction_conjecture type Cognition100023271.
- New_digraph_reconstruction_conjecture type Communication100033020.
- New_digraph_reconstruction_conjecture type Concept105835747.
- New_digraph_reconstruction_conjecture type Conjectures.
- New_digraph_reconstruction_conjecture type Content105809192.
- New_digraph_reconstruction_conjecture type DirectedGraphs.
- New_digraph_reconstruction_conjecture type Graph107000195.
- New_digraph_reconstruction_conjecture type Hypothesis105888929.
- New_digraph_reconstruction_conjecture type Idea105833840.
- New_digraph_reconstruction_conjecture type PsychologicalFeature100023100.
- New_digraph_reconstruction_conjecture type Speculation105891783.
- New_digraph_reconstruction_conjecture type VisualCommunication106873252.
- New_digraph_reconstruction_conjecture comment "The reconstruction conjecture of Stanislaw Ulam is one of the best-known open problems in graph theory.".
- New_digraph_reconstruction_conjecture label "New digraph reconstruction conjecture".
- New_digraph_reconstruction_conjecture sameAs m.03y054x.
- New_digraph_reconstruction_conjecture sameAs Q7016399.
- New_digraph_reconstruction_conjecture sameAs Q7016399.
- New_digraph_reconstruction_conjecture sameAs New_digraph_reconstruction_conjecture.
- New_digraph_reconstruction_conjecture wasDerivedFrom New_digraph_reconstruction_conjecture?oldid=604315961.
- New_digraph_reconstruction_conjecture isPrimaryTopicOf New_digraph_reconstruction_conjecture.