New digraph reconstruction conjecture

Directed graphs | Unsolved problems in graph theory | Conjectures

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. (Wikipedia).

Second Order Recurrence Formula (1 of 3: Prologue - considering the old course)

More resources available at www.misterwootube.com

From playlist Further Proof by Mathematical Induction

Solving Higher Degree Trigonometric Equations (2 of 3: Combining results into proof)

More resources available at www.misterwootube.com

From playlist Using Complex Numbers

Recurrence Relation Solution - Intro to Algorithms

This video is part of an online course, Intro to Algorithms. Check out the course here: https://www.udacity.com/course/cs215.

From playlist Introduction to Algorithms

Ran Levi (6/25/17) Bedlewo: Topological analysis of neural networks

A standard way to schematically represent networks in general, and neural network in particular, is as a graph. Depending on context, graphs representing networks can be directed or undirected, and in some cases carry labels or weights on their vertices and edges. With any graph one can as

From playlist Applied Topology in Będlewo 2017

Quantum Mechanics and the Schrödinger Equation

Okay, it's time to dig into quantum mechanics! Don't worry, we won't get into the math just yet, for now we just want to understand what the math represents, and come away with a new and improved view of the electron as both a circular standing wave and a cloud of probability density. Spoo

From playlist Modern Physics

Solving Trigonometric Equations

We solved so many equations when studying algebra. Now that we understand trig functions, as well as inverse trig functions, we are ready to solve trigonometric equations. This will combine an understanding of trigonometry with some of the techniques we learned in algebra, and in the end,

From playlist Trigonometry

Jørgen Bang-Jensen: Antistrong digraphs

Jørgen Bang-Jensen: Antistrong digraphs An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that one can decide in line

From playlist HIM Lectures 2015

Kathryn Hess (6/27/17) Bedlewo: Topology meets neuroscience

I will present an overview of applications of topology to neuroscience on a wide range of scales, from the level of neurons to the level of brain regions. In particular I will describe collaborations in progress with the Blue Brain Project on topological analysis of the structure and funct

From playlist Applied Topology in Będlewo 2017

R. Levi: An application of neighborhoods in directed graphs in the classification of binary dynamics

Speaker: Ran Levi Date: August 30, 2021 Abstract: A binary state on a graph means an assignment of binary values to its vertices. For example, if one encodes a network of spiking neurons as a directed graph, then the spikes produced by the neurons at an instant of time is a binary state on

From playlist Beyond TDA - Persistent functions and its applications in data sciences, 2021

Indegree and Outdegree in Directed Graphs | Graph Theory

We describe the indegrees and the outdegrees of vertices in directed graphs in detail, with examples and practice problems. Recall in a digraph edges have direction, and so are called directed edges or "arcs". These are represented by ordered pairs of vertices like (u,v). The arc (u,v) goe

From playlist Graph Theory

Solving a logarithm with a fraction

👉 Learn how to solve logarithmic equations. Logarithmic equations are equations with logarithms in them. To solve a logarithmic equation, we first isolate the logarithm part of the equation. After we have isolated the logarithm part of the equation, we then get rid of the logarithm. This i

From playlist Solve Logarithmic Equations

First Order Linear Recurrence Relations

From playlist N. Proofs and Recurrence Relations

Using the inverse of an exponential equation to find the logarithm

👉 Learn how to convert an exponential equation to a logarithmic equation. This is very important to learn because it not only helps us explain the definition of a logarithm but how it is related to the exponential function. Knowing how to convert between the different forms will help us i

From playlist Logarithmic and Exponential Form | Learn About

Interdisciplinarity in the Age of Networks - Jennifer Chayes

Jennifer Chayes Managing Director, Microsoft Research New England, Microsoft Research New York May 21, 2013 For more videos, visit http://video.ias.edu

From playlist Mathematics

Lozenge Tilings and the Gaussian Free Field on a Cylinder - Marianna Russkikh

Probability Seminar Lozenge Tilings and the Gaussian Free Field on a Cylinder Marianna Russkikh California Institute of Technology Date: November 18, 2022 We discuss new results on lozenge tilings on an infinite cylinder, which may be analyzed using the periodic Schur process introduced

From playlist Mathematics

Sarah Morell: Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds

In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, we ask for an unsplitta

From playlist Workshop: Approximation and Relaxation

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Sale...- Ola Svensson

Computer Science/Discrete Mathematics Seminar II Topic: A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem Speaker: Ola Svensson Affiliation: École polytechnique fédérale de Lausanne Date: January 23, 2018 For more videos, please visit http://video.ia

From playlist Mathematics

What is the Riemann Hypothesis?

This video provides a basic introduction to the Riemann Hypothesis based on the the superb book 'Prime Obsession' by John Derbyshire. Along the way I look at convergent and divergent series, Euler's famous solution to the Basel problem, and the Riemann-Zeta function. Analytic continuation

From playlist Mathematics

Yanqi Qiu: Determinantal point processes and spaces of holomorphic functions

The determinantal point processes arise naturally from different areas such as random matrices, representation theory, random graphs and zeros of holomorphic functions etc. In this talk, we will briefly talk about determinantal point processes related to spaces of holomorphic functions, i

From playlist Probability and Statistics

Solving a simple logarithm

From playlist Solve Logarithmic Equations

New digraph reconstruction conjecture

Related pages