Characterization of (𝑟,𝑠)-adjacency graphs of complexes

Gardner, Marianne; Harary, Frank

doi:10.1090/S0002-9939-1981-0620016-8

Characterization of $(r, s)$-adjacency graphs of complexes
HTML articles powered by AMS MathViewer

by Marianne Gardner and Frank Harary PDF

Proc. Amer. Math. Soc. 83 (1981), 211-214 Request permission

Abstract:

The $(r,s)$-adjacency graph of a simplicial complex $K$ has been defined as the graph whose nodes are the $r$-cells of $K$ with adjacency whenever there is incidence with a common $s$-cell. The $(r,s)$-adjacency graphs for $r > s$ have been characterized by graph coverings by Dewdney and Harary generalizing the result of Krausz for line-graphs $(r = 1,s = 0)$. We now complete the characterization by handling the case $r < s$.

References

J. C. Bermond, M. C. Heydemann, and D. Sotteau, Line graphs of hypergraphs. I, Discrete Math. 18 (1977), no. 3, 235–241. MR 463003, DOI 10.1016/0012-365X(77)90127-3
J.-C. Bermond, A. Germa, and M.-C. Heydemann, Graphes représentatifs d’hypergraphes, Cahiers Centre Études Rech. Opér. 20 (1978), no. 3-4, 325–329 (French, with English summary). MR 543175
A. K. Dewdney and Frank Harary, The adjacency graphs of a complex, Czechoslovak Math. J. 26(101) (1976), no. 1, 137–144. MR 427152, DOI 10.21136/CMJ.1976.101380
M. L. Gardner, Forbidden configurations in intersection graphs of $r$-graphs, Discrete Math. 31 (1980), no. 1, 85–88. MR 578064, DOI 10.1016/0012-365X(80)90175-2

Forbidden configurations of large girth for intersection graphs of hypergraphs

Branko Grünbaum, Incidence patterns of graphs and complexes, The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) Springer, Berlin, 1969, pp. 115–128. MR 0250920
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
M.-C. Heydemann and D. Sotteau, Line-graphs of hypergraphs. II, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 567–582. MR 519291
J. Krausz, Démonstration nouvelle d’une théorème de Whitney sur les réseaux, Mat. Fiz. Lapok 50 (1943), 75–85 (Hungarian, with French summary). MR 18403