Home » Subject » Graph Theory » Basic G.T.
Importance: Medium ✭✭
Author(s): Graham, Ronald L.
Subject: Graph Theory
» Basic Graph Theory
Keywords: reconstruction
tree
Recomm. for undergrads: no
Posted by: mdevos
on: March 18th, 2007
Problem   for every graph $ G $, we let $ L(G) $ denote the line graph of $ G $. Given that $ G $ is a tree, can we determine it from the integer sequence $ |V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots $?

Graph reconstruction is a notoriously difficult subject. This conjecture is an unusual type of reconstruction problem where our class of graphs is very limited - just trees, but we are also given relatively little information - just a sequence of integers.

Bibliography

[GR] C. Godsil and G. Royle, Algebraic graph theory. Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001 (page 18).


* indicates original appearance(s) of problem.
5 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options