تقرير
Neighborhood reconstruction and cancellation of graphs
| العنوان: | Neighborhood reconstruction and cancellation of graphs |
|---|---|
| المؤلفون: | Hammack, Richard H., Mullican, Cristina |
| المصدر: | Electron. J. Combin. 24 (2017), no. 2, Paper 2.8, 11 pp |
| سنة النشر: | 2016 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C76, 05C60 |
| الوصف: | We connect two seemingly unrelated problems in graph theory. Any graph $G$ has an associated neighborhood multiset $\mathscr{N}(G)= \{N(x) \mid x\in V(G)\}$ whose elements are precisely the open vertex-neighborhoods of $G$. In general there exist non-isomorphic graphs $G$ and $H$ for which $\mathscr{N}(G)=\mathscr{N}(H)$. The neighborhood reconstruction problem asks the conditions under which $G$ is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which $\mathscr{N}(G)=\mathscr{N}(H)$ implies $G\cong H$. Such a graph is said to be neighborhood-reconstructible. The cancellation problem for the direct product of graphs seeks the conditions under which $G\times K\cong H\times K$ implies $G\cong H$. Lovasz proved that this is indeed the case if $K$ is not bipartite. A second instance of the cancellation problem asks for conditions on $G$ that assure $G\times K\cong H\times K$ implies $G\cong H$ for any bipartite graph $K$ with $E(K)\neq \emptyset$. A graph $G$ for which this is true is called a cancellation graph. We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction. Comment: 11 pages, 6 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1612.02717 |
| رقم الأكسشن: | edsarx.1612.02717 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |