Questions tagged [graph-reconstruction]
Questions related to graph reconstruction, the problem of reconstructing a graph from a set or deck (multiset) of subgraphs.
19
questions
23
votes
0
answers
481
views
Is the Poset of Graphs Automorphism-free?
For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
Is ...
17
votes
1
answer
868
views
Reconstruction Conjecture holds for Directed Acyclic Graphs?
Wikipedia's article on the Reconstruction Conjecture mentions that the conjecture is false for digraphs, and refers to two papers by Stockmeyer. As far as I can see, none of the counter-examples in ...
- 3,620
14
votes
0
answers
510
views
Reconstruction conjecture and partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 281
13
votes
1
answer
397
views
Reconstruction Conjecture: are almost all digraphs reconstructible?
The Reconstruction Conjecture for simple graphs remains unresolved. Most attempts I've seen at resolving the conjecture aim at proving it to be true (or partially true). I don't believe there is a ...
- 1,327
10
votes
1
answer
1k
views
Reconstruction conjecture: Can other decks do the job?
The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.
Question: Have other decks been investigated, finding out
that only vertex-...
- 9,548
8
votes
5
answers
884
views
Reconstructing graphs with vertices of degree $k$ and $k-1$
The Graph Reconstruction Conjecture claims that any simple graph with 3 or more vertices is reconstructible from its "deck" of vertex-deleted subgraphs. (A nice introduction to this problem is at this ...
- 931
6
votes
1
answer
885
views
Reconstruction Conjecture: Group theoretic formulation
As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs.
Is there a group-theoretic formulation of this conjecture?
...
- 2,787
5
votes
1
answer
205
views
Reconstructing the number of Hamiltonian cycles
As is common terminology in graph reconstruction, given a graph $G$, we call a vertex deleted subgraph of $G$, a card, and call the multiset of all cards, the deck of $G$. The graph reconstruction ...
- 84.6k
4
votes
1
answer
84
views
From equivalent graphs to isomorphic one- Reconstruction Conjecture
Suppose we are working with connected simple graphs.
We say the graph $G$ and $H$ are equivalent if for any spanning tree $T_G$ in $G$ there is an spanning tree $T_H$ in $H$ such that $T_G$ is ...
- 4,738
4
votes
1
answer
878
views
Edge Reconstruction Conjecture
I have seen this question asked at least once before, but not with any real answers.
I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction ...
4
votes
1
answer
278
views
If a graph invariant is NP-Hard, is its "deck ratio" NP-Hard as well?
This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define $D_{\psi}(G)...
- 6,832
4
votes
0
answers
80
views
Determined labels and reconstruction conjecture
In the reconstruction conjecture $(RC)$, if we know the $k$, $0\leq k \leq n$ labels of the vertices, then $RC$ is true.
Do we know the minimum $k$ that the above statement is true?
Do we have any ...
- 4,738
4
votes
0
answers
147
views
Relation between two conjectures on reconstruction of graphs
In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...
- 4,738
3
votes
2
answers
184
views
Less general edge reconstruction problem for simple graphs
Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of (...
- 39
3
votes
2
answers
227
views
Efficiently generating all regular/bidegreed graphs
There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total ...
- 131
3
votes
0
answers
97
views
Reconstructing a function from its variants that negate one argument
Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
- 37k
1
vote
2
answers
279
views
edge graph reconstruction conjecture : set vs multi set
Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...
0
votes
0
answers
64
views
Large family of subsets with small pairwise intersections
(Crossposting from StackExchange 4799692 after it has been there for a while.)
Let $\alpha>0$ be a constant (can be sufficiently small if necessary) and $n$ be sufficiently large. What can we say ...
- 41
0
votes
0
answers
142
views
Reconstruction conjecture:Complete graph invariants
Suppose we have a complete graph invariant $I$ i.e. for any two graphs $G$ and $H$ we have $ I(G)=I(H) \iff G \cong H $.
Suppose now that the invariant $I$ is reconstructible from the desk of $G.$ ...
- 546