Maximum Genus, Independence Number and Girth

Abstract

It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.

Keywords

Maximum genus / Betti deficiency / Independence number / Girth / 05C / O157.5

References

[1] Bondy, J. A. & Murty, U. S. R., Graph theory with application, MacMillan, London, 1976.

[2] Liu, Y., Embeddability in graphs, Science, Beijing, 1994.

[3] Nordhaus E, Stewart B, White A. On the maximum genus of a graph. J. Combinatorial Theory B, 1979, 26: 217-225

[4] Xuong H N. Upper embeddable graphs and related topics. J. Combinatorial Theory B, 1979, 26: 226-232

[5] Nebeský L. A new characterization of the maximum genus of graphs. J. Czechoslovak Math., 1981, 31(106): 604-613

[6] Chen J, Archdeacon D, Gross J L. Maximum genus and connectivity. Discrete Mathematics, 1996, 149: 19-29

[7] Chen J, Kanchi S P, Gross J L. A tight lower bound on the maximum genus of a simplicial graph. Discrete Mathematics, 1996, 156: 83-102

[8] Kanchi, S. P. & Chen, J., Tight lower bound on the maximum genus of a 2-connected simplicial graph, Manuscript, 1992.

[9] Škoveria M. The maximum genus of graph of diameter two. Discrete Mathematics, 1991, 87: 175-180

[10] Linfu H, Mingchun T. The maximum genus of diameter three. Australasian Journal of Combinatorics, 1996, 14: 187-171

[11] Nedeal N, Škoveria M. Bodenierk R, Henn R. On upper embeddable graphs with short faces. Topics in combinatorics and graph theory, 1990, Heidelberg: Physicaverlay 519-529

[12] Huang Y, Liu Y. The upper embeddability of graphs. Science in China, Series A, 1998, 28(3): 223-228

[13] Huang Y, Liu Y. The maximum genus and 2-factors of graphs. Chin. Ann. of Math., 1997, 18A(5): 587-596

[14] Huang Y, Liu Y. Maximum genus and maximum nonseparating independent set of a 3-regular graph. Discrete Mathematics, 1997, 176: 149-158