























Kelly's lemma is a basic result on graph reconstruction. It states that given the deck of a graph $G$ on $n$ vertices, and a graph $F$ on fewer than $n$ vertices, we can count the number of subgraphs of $G$ that are isomorphic to $F$. Moreover, for a given card $G-v$ in the deck, we can count the number of subgraphs of $G$ that are isomorphic to $F$ and that contain $v$. We consider the problem of refining the lemma to count rooted subgraphs such that the root vertex coincides the deleted vertex. We show that such counting is not possible in general, but a multiset of rooted subgraphs of a fixed height $k$ can be counted if $G$ has radius more than $k$. We also prove a similar result for the edge reconstruction problem.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。