<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 2" %>
Subgraphs with Restricted Degrees of Their Vertices in Polyhedral Maps on Compact 2-Manifolds
S. Jendrol1 and H.-J. Voss2
1Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
jendrol@kosice.upjs.sk
2Departmen of Algebra, Technical University Dresden, Mommsenstrasse 13, 01062 Dresden, Germany
voss@math.tu-dresden.de
Annals of Combinatorics 5 (2) p.211-226 June, 2006
AMS Subject Classification: 05C10
Abstract:
Let $ \mathcal H(k,\, \mathbb{M})$ be the family of all polyhedral maps of order at least $ k$ on a compact 2-manifold $ \mathbb{M}$ of Euler characteristic $ \chi
(\mathbb{M})$. We investigate the minimum integer $ \tau (k,\,
\mathbb{M})$ such that any map $ G \in \mathcal H(k,\, \mathbb{M})$ contains a connected subgraph $ H$ of order $ k$ for which $ \deg_G
(A) \leq \tau (k,\, \mathbb{M})$ holds for every vertex $ A$ of $ H$. We prove that if $ \chi(\mathbb{M})<0$ then for $ k\geq 4$

$\displaystyle \Big\lfloor \frac {2k+2}{3} \Big\rfloor \Big\lgroup \Big\lfloor \...
...eq \Big\lfloor (k+1)
\frac {5+ \sqrt {49-24 \chi (\mathbb{M})}}{3} \Big\rfloor.$

The upper bound is tight for every $ k \equiv 2$ (mod 3) and infinitely many orientable as well as infinitely many nonorientable surfaces.
Keywords: graph, embedding, polyhedral map, light subgraph, structural properties of embedded graphs

References:

1.  I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3- connected graphs, Graphs Combin. 13 (1997) 245–250.

2.  I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar graphs, Discrete Math. 191 (1998) 83–90.

3.  B. Grünbaum, Convex Polytopes, Interscience, New York, 1967.

4.  B. Grünbaum and G. C. Shephard, Analogues for tiling of Kotzig's theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982) 129–140.

5.  J. Ivanco, The weight of a graph, Ann. Discrete Math. 51 (1992) 113–116.

6.  S. Jendrol', On face vectors of trivalent maps, Math. Slovaca 36 (1986) 367–386.

7.  S. Jendrol' and H.-J. Voss, A local property of polyhedral maps on compact 2-dimensional manifolds, Discrete Math. 212 (2000) 111–120.

8.  S. Jendrol' and H.-J. Voss, A local property of large polyhedral maps on compact 2- dimensional manifolds, Graphs Combin. 15 (1999) 303–313.

9.  S. Jendrol' and H.-J. Voss, Light paths with an odd number of vertices in large polyhedral maps, Ann. Combin. 2 (1998) 313–324.

10.  S. Jendrol' and H.-J. Voss, Light paths with an odd number of vertices in polyhedral maps, Czechoslovak Math. J. 50 (2000) 555–564.

11.  S. Jendrol' and H.-J. Voss, Subgraphs with restricted degrees of their vertices in large polyhedral maps on compact 2-manifolds, Europ. J. Combin. 20 (1999) 821–832.

12.  A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Cäs. SAV (Math. Slovaca) 5 (1955) 111–113.

13.  A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569–570.

14.  B. Mohar, Face-width of embedded graphs, Math. Slovaca 47 (1997) 35–63.

15.  G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.

16.  N. Robertson and R. P. Vitray, Representativity of surface embeddings, In: Paths, Flows and VLSI-Layout, B. Korte, L. Lovász, H.J. Prőmel, and A. Schrijver, Eds., Springer-Verlag, Berlin - New York, 1990.

17.  H. Sachs, Einführung in die Theorie der endlichen Graphen Teil II, Teubner Leipzig, 1972.

18.  C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635.

19.  A.T. White, The proof of the Heawood conjecture, In: Selected Topics in Graph Theory, L.W. Beineke and R.J. Wilson, Eds., Academic Press, London, 1978, pp. 51–81.

20.  A.T. White and L.W. Beineke, Topological graph theory, In: Selected Topic in Graph Theory, L.W. Beineke and R.J. Wilson, Eds., Academic Press, London, 1978, pp. 15–49.

21.  J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281–296.