Article ID Journal Published Year Pages File Type
4649438 Discrete Mathematics 2009 7 Pages PDF
Abstract

Let G=(V,E,F)G=(V,E,F) be a 3-connected simple graph imbedded into a surface SS with vertex set VV, edge set EE and face set FF. A face αα is an 〈a1,a2,…,ak〉〈a1,a2,…,ak〉-face if αα is a kk-gon and the degrees of the vertices incident with αα in the cyclic order are a1,a2,…,aka1,a2,…,ak. The lexicographic minimum 〈b1,b2,…,bk〉〈b1,b2,…,bk〉 such that αα is a 〈b1,b2,…,bk〉〈b1,b2,…,bk〉-face is called the typetype of αα.Let zz be an integer. We consider zz-oblique graphs, i.e. such graphs that the number of faces of each type is at most zz. We show an upper bound for the maximum vertex degree of any zz-oblique graph imbedded into a given surface. Moreover, an upper bound for the maximum face degree is presented. We also show that there are only finitely many oblique graphs imbedded into non-orientable surfaces.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,