Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Characterization of $ (r,\,s)$-adjacency graphs of complexes

Authors: Marianne Gardner and Frank Harary
Journal: Proc. Amer. Math. Soc. 83 (1981), 211-214
MSC: Primary 05C75; Secondary 05C65, 05C99
MathSciNet review: 620016
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] J. C. Bermond, M. C. Heydemann, and D. Sotteau, Line graphs of hypergraphs. I, Discrete Math. 18 (1977), no. 3, 235–241. MR 0463003
  • [2] 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). Colloque Mathématiques Discrètes: Codes et Hypergraphes (Brussels, 1978). MR 543175
  • [3] A. K. Dewdney and Frank Harary, The adjacency graphs of a complex, Czechoslovak Math. J. 26(101) (1976), no. 1, 137–144. MR 0427152
  • [4] M. L. Gardner, Forbidden configurations in intersection graphs of 𝑟-graphs, Discrete Math. 31 (1980), no. 1, 85–88. MR 578064, 10.1016/0012-365X(80)90175-2
  • [5] -, Forbidden configurations of large girth for intersection graphs of hypergraphs, Ars Combinatoria (submitted).
  • [6] 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
  • [7] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
  • [8] 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
  • [9] 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 0018403

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C75, 05C65, 05C99

Retrieve articles in all journals with MSC: 05C75, 05C65, 05C99

Additional Information

Article copyright: © Copyright 1981 American Mathematical Society