Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T00:29:32.382Z Has data issue: false hasContentIssue false
  • English
  • Français

On Homeomorphic Embeddings of Km,n in the Cube

Published online by Cambridge University Press:  20 November 2018

Jehuda Hartman
Jehuda Hartman*
Affiliation:
The University of Alberta, Edmonton, Alberta
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Homeomorphic embeddings of Knin the m-cube were investigated in [6]. In particular, it was proved that any homeomorph of Kn+1embedded in the m-cube has at least n2edges. Furthermore, homeomorphic embeddings of Kn+1having exactly n2edges are unique up to isomorphism. In this paper a similar problem for the complete bipartite graph is considered.

We adopt the notation and terminology of [5].

All graphs considered are without loops and multiple edges.

Let x = uv be an edge of a graph G; x will be called subdivided if it is replaced by a vertex ω and by edges uω and ωv. A graph G’ is called a subdivision of G if it is obtained from G by a subdivision of an edge of G. A refinement Ĝ of G, is a graph isomorphic to a graph obtained from G by a finite sequence of subdivisions.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 32 , Issue 3 , 01 June 1980 , pp. 644 - 652
Copyright
Copyright © Canadian Mathematical Society 1980

References

1. Beineke, L. W. and Chartrand, G., The coarseness of a graph, Composito Math. (1966), 290–298.Google Scholar
2. Beineke, L. W. and Guy, R. K., The coarseness of the complete bipartite graph, Can. J. Math. 21 (1969), 1086–1096.Google Scholar
3. Guy, R. K. and Beineke, L. W., The coarseness of the complete graph, Can. J. Math. (1968), 888–894.Google Scholar
4. Guy, R. K., A coarseness conjecture of Erdos, J. Comb. Th. 3 (1967), 38–42.Google Scholar
5. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969).Google Scholar
6. Hartman, J., The homeomorphic embedding of Kn in the m-cube, Discrete Mathematic. 16 (1976), 157–160.Google Scholar