Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; neighbor; neighborhood hypergraph; clique hypergraph
graph; neighbor; neighborhood hypergraph; clique hypergraph
Summary:
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$.
References:
[1] Berge C.: Hypergraphs. North-Holland, Amsterdam, 1989. MR 1013569 | Zbl 0851.05080
[2] Berge C.: Graphs and Hypergraphs. North-Holland, Amsterdam, 1973. MR 0357172 | Zbl 0483.05029
[3] Berge C., Duchet P.: A generalization of Gilmore's theorem. Recent Advances in Graph Theory, (Fiedler M., ed.), Academia, Prague, 1975, pp.49-55. MR 0406801 | Zbl 0325.05125
[4] Erdös P., Gallai T., Tuze Z.: Covering the cliques of a graph with vertices. Discrete Math. 108 (1992), 279-289. MR 1189850
[5] Jensen T.R., Toft B.: Graph Coloring Problems. Wiley Interscience, New York, 1995. MR 1304254 | Zbl 0855.05054
[6] Prisner E.: Intersection multigraphs of uniform hypergraphs. Graphs Combin. 14 (1998), 4 363-375. MR 1658849 | Zbl 0910.05048
Search
Partner of
