Hostname: page-component-76fb5796d-skm99 Total loading time: 0 Render date: 2024-04-27T04:04:29.813Z Has data issue: false hasContentIssue false
  • English
  • Français

Inequalities involving the genus of a graph and its thicknesses†

Published online by Cambridge University Press:  18 May 2009

Lowell W. Beineke  and
Frank Harary
Lowell W. Beineke
Affiliation:
University of Michigan Ann Arbor, Michigan, U.S.A.
Frank Harary
Affiliation:
University of Michigan Ann Arbor, Michigan, U.S.A.
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.

Let G be a graph with p points and q lines, and genus γ. The thicknesst(G) has been introduced as the minimum number of planar subgraphs whose union is G. This topological invariant of a graph has been studied by Battle, Harary and Kodama [1], Tutte [7], Beineke, Harary and Moon [3], and Beineke and Harary [2].

It is natural to generalise this concept of the thickness of a graph to the union of graphs with a specified genus. We say that the n-thickness of G is the minimum number of subgraphs of genus at most n whose union is G. Denoting the n-thickness of G by tn, we write in particular t0 the 0-thickness, i.e., the thickness.

Type
Research Article
Information
Glasgow Mathematical Journal , Volume 7 , Issue 1 , January 1965 , pp. 19 - 21
Copyright
Copyright © Glasgow Mathematical Journal Trust 1965

References

REFERENCES

1.Battle, J., Harary, F., and Kodoma, Y., Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962), 569–571.CrossRefGoogle Scholar
2.Beineke, L. W. and Harary, F., On the thickness of a complete graph. Bull. Amer. Math. Soc. 70 (1964), 618–620.CrossRefGoogle Scholar
3.Beineke, L. W., Harary, F. and Moon, J. W., On the thickness of the complete bipartite graph, Proc. Camb. Phil. Soc. 60 (1964), 1–5.CrossRefGoogle Scholar
4.Errera, A., Une conséquence d'un théorème de M. Whitney, Acad. Roy. Belg. Bull. Cl. Sci. 36 (1950), 594–596.Google Scholar
5.Harary, F., A complementary problem on nonplanar graphs, Math. Mag. 35 (1962), 301–303.CrossRefGoogle Scholar
6.König, D., Theorie der endlichen und unendlichen Graphen (Leipzig, 1936; reprinted New York, 1950).Google Scholar
7.Tutte, W. T., The non-biplanar character of the complete 9-graph, Canad. Math. Bull. 6 (1963), 319–330.CrossRefGoogle Scholar