| Title:
|
On a property of neighborhood hypergraphs (English) |
| Author:
|
Pióro, Konrad |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
47 |
| Issue:
|
1 |
| Year:
|
2006 |
| Pages:
|
149-154 |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
graph |
| Keyword:
|
neighbor |
| Keyword:
|
neighborhood hypergraph |
| Keyword:
|
clique hypergraph |
| MSC:
|
05C65 |
| MSC:
|
05C69 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1150.05405 |
| idMR:
|
MR2223974 |
| . |
| Date available:
|
2009-05-05T16:56:18Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119581 |
| . |
| Reference:
|
[1] Berge C.: Hypergraphs.North-Holland, Amsterdam, 1989. Zbl 0851.05080, MR 1013569 |
| Reference:
|
[2] Berge C.: Graphs and Hypergraphs.North-Holland, Amsterdam, 1973. Zbl 0483.05029, MR 0357172 |
| Reference:
|
[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. Zbl 0325.05125, MR 0406801 |
| Reference:
|
[4] Erdös P., Gallai T., Tuze Z.: Covering the cliques of a graph with vertices.Discrete Math. 108 (1992), 279-289. MR 1189850 |
| Reference:
|
[5] Jensen T.R., Toft B.: Graph Coloring Problems.Wiley Interscience, New York, 1995. Zbl 0855.05054, MR 1304254 |
| Reference:
|
[6] Prisner E.: Intersection multigraphs of uniform hypergraphs.Graphs Combin. 14 (1998), 4 363-375. Zbl 0910.05048, MR 1658849 |
| . |
