Konrad Pi\'oro
On a property of neighborhood hypergraphs

Comment.Math.Univ.Carolinae 47,1 (2006) 149-154.

Abstract:The aim of the paper is to show that no simple graph has a proper subgraph with the same neighborhood hypergraph. As a simple consequence of this result we infer that if a clique hypergraph $\Cal G$ and a hypergraph $\Cal H$ have the same neighborhood hypergraph and the neighborhood relation in $\Cal G$ is a subrelation of such a relation in $\Cal H$, then $\Cal H$ is inscribed into $\Cal G$ (both seen as coverings). In particular, if $\Cal H$ is also a clique hypergraph, then $\Cal H = \Cal G$.

Keywords: graph, neighbor, neighborhood hypergraph, clique hypergraph
AMS Subject Classification: 05C99, 05C69, 05C65

PDF