Premium
Reconstructing trees from two cards
Author(s) -
Welhan Manuel
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20424
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , tree (set theory) , deck , graph , discrete mathematics , class (philosophy) , computer science , artificial intelligence , structural engineering , engineering
Let be the class of unlabeled trees. An unlabeled vertex‐deleted subgraph of a tree T is called a card. A collection of cards is called a deck. We say that the tree T has a deck D if each card in D can be obtained by deleting distinct vertices of T . If T is the only unlabeled tree that has the deck D , we say that T is ‐reconstructible from D . We want to know how large of a deck D is necessary for T to be ‐reconstructible. We define rn( T ) as the minimum number of cards in a deck D such that T is ‐reconstructible from D . It is known that rn( T )≤3, but it is conjectured that rn( T )≤2 for all trees T . We prove that the conjecture holds for all homeomorphically irreducible trees. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 243–257, 2010