Neighborhood reconstruction and cancellation of graphs

zbMATH Open1361.05111arXiv1612.02717MaRDI QIDQ528982FDOQ528982

Authors: Richard H. Hammack, Cristina Mullican 

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We connect two seemingly unrelated problems in graph theory. Any graph $G$ has an associated neighborhood multiset $mathscrN(G)=N(x)midxinV(G)$ whose elements are precisely the open vertex-neighborhoods of $G$. In general there exist non-isomorphic graphs $G$ and $H$ for which $mathscrN(G)=mathscrN(H)$. The neighborhood reconstruction problem asks the conditions under which $G$ is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which $mathscrN(G)=mathscrN(H)$ implies $GcongH$. Such a graph is said to be neighborhood-reconstructible. The cancellation problem for the direct product of graphs seeks the conditions under which $GimesKcongHimesK$ implies $GcongH$. 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 $GimesKcongHimesK$ implies $GcongH$ for any bipartite graph $K$ with $E(K)eqemptyset$. 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.

Full work available at URL: https://arxiv.org/abs/1612.02717

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Graph exponentiation and neighborhood reconstruction
• On direct product cancellation of graphs
• A cancellation property for direct product
• A remark on cancellation in direct products of graphs
• A quasicancellation property for the direct product of graphs

zbMATH Keywords

graph productsgraph reconstruction

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Handbook of product graphs
• Realizability and uniqueness in graphs
• Two-fold automorphisms of graphs
• On direct product cancellation of graphs
• Digraphs having the same canonical double covering
• Cancellation of digraphs over the direct product
• On the cancellation law among finite relational structures
• Direct product factorization of bipartite graphs with bipartition-reversing involutions
• Unstable graphs: A fresh outlook via TF-automorphisms

Cited In (7)

• Graph exponentiation and neighborhood reconstruction
• Reconstructing a Graph from its Neighborhood Lists
• A remark on cancellation in direct products of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reconstruction of the neighborhood deck of an ordered set

This page was built for publication: Neighborhood reconstruction and cancellation of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528982)