On a property of neighborhood hypergraphs
Commentationes Mathematicae Universitatis Carolinae (2006)
- Volume: 47, Issue: 1, page 149-154
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topPióro, Konrad. "On a property of neighborhood hypergraphs." Commentationes Mathematicae Universitatis Carolinae 47.1 (2006): 149-154. <http://eudml.org/doc/249872>.
@article{Pióro2006,
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 $\mathcal \{G\}$ and a hypergraph $\mathcal \{H\}$ have the same neighborhood hypergraph and the neighborhood relation in $\mathcal \{G\}$ is a subrelation of such a relation in $\mathcal \{H\}$, then $\mathcal \{H\}$ is inscribed into $\mathcal \{G\}$ (both seen as coverings). In particular, if $\mathcal \{H\}$ is also a clique hypergraph, then $\mathcal \{H\} = \mathcal \{G\}$.},
author = {Pióro, Konrad},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph; neighbor; neighborhood hypergraph; clique hypergraph; graph; neighbor; clique hypergraph},
language = {eng},
number = {1},
pages = {149-154},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On a property of neighborhood hypergraphs},
url = {http://eudml.org/doc/249872},
volume = {47},
year = {2006},
}
TY - JOUR
AU - Pióro, Konrad
TI - On a property of neighborhood hypergraphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2006
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 47
IS - 1
SP - 149
EP - 154
AB - 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 $\mathcal {G}$ and a hypergraph $\mathcal {H}$ have the same neighborhood hypergraph and the neighborhood relation in $\mathcal {G}$ is a subrelation of such a relation in $\mathcal {H}$, then $\mathcal {H}$ is inscribed into $\mathcal {G}$ (both seen as coverings). In particular, if $\mathcal {H}$ is also a clique hypergraph, then $\mathcal {H} = \mathcal {G}$.
LA - eng
KW - graph; neighbor; neighborhood hypergraph; clique hypergraph; graph; neighbor; clique hypergraph
UR - http://eudml.org/doc/249872
ER -
References
top- Berge C., Hypergraphs, North-Holland, Amsterdam, 1989. Zbl0851.05080MR1013569
- Berge C., Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. Zbl0483.05029MR0357172
- Berge C., Duchet P., A generalization of Gilmore's theorem, Recent Advances in Graph Theory, (Fiedler M., ed.), Academia, Prague, 1975, pp.49-55. Zbl0325.05125MR0406801
- Erdös P., Gallai T., Tuze Z., Covering the cliques of a graph with vertices, Discrete Math. 108 (1992), 279-289. (1992) MR1189850
- Jensen T.R., Toft B., Graph Coloring Problems, Wiley Interscience, New York, 1995. Zbl0855.05054MR1304254
- Prisner E., Intersection multigraphs of uniform hypergraphs, Graphs Combin. 14 (1998), 4 363-375. (1998) Zbl0910.05048MR1658849
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.