Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices
Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices
复制标题
对于具有至少七个顶点的图，度列表和连通性是 3-可重构的
DOI：
10.1007/s00373-020-02131-6
复制
发表时间：
2019-04
影响因子：
0.7
通讯作者：
Zirlin Dara
中科院分区：
文献类型：
--
作者：
Kostochka Alex;r V.;Nahvi Mina;West Douglas B.;Zirlin Dara
图的k-甲板是由k个顶点导出的子图的多集。一个图或图的性质是l-可重构的，如果它是由删除l个顶点得到的子图的甲板确定的。证明了当n ≥ 7时，n-顶点图的度表是3-可重构的，且n上的阈值是尖锐的.利用这个结果，我们证明了当n >= 7-deck也决定了一个n-顶点图是否连通;这也是尖锐的。这些结果分别推广了Chernyak和Manvel的结果，即当n >= 6时，度表和连通性是2-可重构的，这两个结果也是尖锐的.
The k-deck of a graph is the multiset of its subgraphs induced by k vertices. A graph or graph property is l-reconstructible if it is determined by the deck of subgraphs obtained by deleting l vertices. We show that the degree list of an n-vertex graph is 3-reconstructible when n >= 7, and the threshold on n is sharp. Using this result, we show that when n >= 7-deck also determines whether an n-vertex graph is connected; this is also sharp. These results extend the results of Chernyak and Manvel, respectively, that the degree list and connectedness are 2-reconstructible when n >= 6, which are also sharp.
登录
查看更多内容
DOI：
--
发表时间：
1960
期刊：
--
影响因子：
--
作者：
S. Ulam
通讯作者：
S. Ulam
DOI：
10.1016/0012-365x(74)90064-8
发表时间：
1974-04
期刊：
Discret. Math.
影响因子：
--
作者：
B. Manvel
通讯作者：
B. Manvel
影响因子：
0.9
作者：
Hannah Spinoza;D. West
通讯作者：
Hannah Spinoza;D. West
影响因子：
0.6
作者：
P. Kelly
通讯作者：
P. Kelly
DOI：
10.1007/bfb0059425
发表时间：
1971
期刊：
--
影响因子：
--
作者：
P. Chinn
通讯作者：
P. Chinn