Reconstruction from the deck of k ‐vertex induced subgraphs
Reconstruction from the deck of k ‐vertex induced subgraphs
复制标题
DOI：
10.1002/jgt.22409
复制
发表时间：
2018-10
影响因子：
0.9
通讯作者：
Hannah Spinoza;D. West
中科院分区：
文献类型：
--
作者：
Hannah Spinoza;D. West
图的k-层是由k个顶点诱导的子图的多个集合；我们研究从它的k-层可以推导出图的什么。通过证明ℓ∈N的一个结果，证明了当n足够大(n>；2ℓ(ℓ+1)2时，(n−ℓ)层决定n点图是否连通(当≥=3时，nℓ25满足，而n≤2 L不满足)。具有n个顶点的图G的可重构性ρ(G)是最大的ℓ，使得G由它的(n−ℓ)-层决定。我们证明了几乎所有图的ρ(G)≥(1−o(1))n/2，从而推广了BollobáS的一个结果。作为Minρ(G)的一个上界，我们有ρ(Cn)=⌈n/2⌉=ρ(Pn)+1。更一般地，当ρ(G)=2时，我们计算Δ(G)，这涉及到推广Stanley的一个结果。最后，我们证明了一个完全的r-部图可以从它的(r+1)-层重构。
The k ‐ deck of a graph is its multiset of subgraphs induced by k vertices; we study what can be deduced about a graph from its k ‐deck. We strengthen a result of Manvel by proving for ℓ ∈ N that when n is large enough ( n > 2 ℓ ( ℓ + 1 ) 2 suffices), the ( n − ℓ ) ‐deck determines whether an n ‐vertex graph is connected ( n ≥ 25 suffices when ℓ = 3 , and n ≤ 2 l cannot suffice). The reconstructibility ρ ( G ) of a graph G with n vertices is the largest ℓ such that G is determined by its ( n − ℓ ) ‐deck. We generalize a result of Bollobás by showing ρ ( G ) ≥ ( 1 − o ( 1 ) ) n ∕ 2 for almost all graphs. As an upper bound on min ρ ( G ) , we have ρ ( C n ) = ⌈ n ∕ 2 ⌉ = ρ ( P n ) + 1 . More generally, we compute ρ ( G ) whenever Δ ( G ) = 2 , which involves extending a result of Stanley. Finally, we show that a complete r ‐partite graph is reconstructible from its ( r + 1 ) ‐deck.