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 and a hypergraph have the same neighborhood hypergraph and the neighborhood relation in is a subrelation of such a relation in , then is inscribed into (both seen as coverings). In particular, if is also a clique hypergraph, then .
In this note we extend results on the covering graphs of modular lattices (Zelinka) and semimodular lattices (Gedeonova, Duffus and Rival) to the covering graph of certain graded lattices.
An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider the embeddable (n,n)-graphs. We prove that with few exceptions the corresponding permutation may be chosen as cyclic one.
In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.