On $l$-reconstructibility of degree list of graphs

	On $l$-reconstructibility of degree list of graphs
AUT Journal of Mathematics and Computing
مقاله 5، دوره 5، شماره 1، 2024، صفحه 39-44 اصل مقاله (398.78 K)
نوع مقاله: Original Article
شناسه دیجیتال (DOI): 10.22060/ajmc.2023.21822.1112
نویسندگان
Rajab Ali Borzooei^* ؛ Mehrnoosh Shadravan
Department of Mathematics, Shahid Beheshti University, Tehran, Iran
چکیده
The $k$-deck of a graph is the multiset of its subgraphs induced by $k$ vertices which is denoted by $D_{k}(G)$. A graph or graph property is $l$-reconstructible if it is determined by the deck of subgraphs obtained by deleting $l$ vertices. Manvel proved that from the $(n-l)$-deck of a graph and the numbers of vertices with degree $i$ for all $i$, $n-l \leq i \leq n-1$, the degree list of the graph is determined. In this paper, we extend this result and prove that if $G$ is a graph with $n$ vertices, then from the $(n-l)$-deck of $G$ and the numbers of vertices with degree $i$ for all $i$, $n-l \leq i \leq n-3$, where $l \geq 4$ and $n \geq l+6$, the degree list of the graph is determined.
کلیدواژه‌ها
Reconstruction؛ $l$-Reconstructibility؛ Degree list
مراجع

آمار تعداد مشاهده مقاله: 623 تعداد دریافت فایل اصل مقاله: 544