Neighborhood reconstruction and cancellation of graphs

MaRDI QIDQ528982zbMATH OpenFDO

Authors Richard H. Hammack, Cristina Mullican

Publication date 18 May 2017

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

Full work available at URL https://arxiv.org/abs/1612.02717, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p8

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

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)

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.

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

Cites work

• Cancellation of digraphs over the direct product
• Digraphs having the same canonical double covering
• Direct product factorization of bipartite graphs with bipartition-reversing involutions
• Handbook of product graphs
• On direct product cancellation of graphs
• On the cancellation law among finite relational structures
• Realizability and uniqueness in graphs
• Two-fold automorphisms of graphs
• 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
• scientific article; zbMATH DE number 6704556 (Why is no real title available?)
• scientific article; zbMATH DE number 1047709 (Why is no real title available?)
• scientific article; zbMATH DE number 1094128 (Why is no real title available?)
• 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)