On the structure of plane graphs of minimum face size 5

Tomás Madaras

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 403-411
  • ISSN: 2083-5892

Abstract

top
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star K 1 , 3 and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.

How to cite

top

Tomás Madaras. "On the structure of plane graphs of minimum face size 5." Discussiones Mathematicae Graph Theory 24.3 (2004): 403-411. <http://eudml.org/doc/270681>.

@article{TomásMadaras2004,
abstract = {A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star $K_\{1,3\}$ and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.},
author = {Tomás Madaras},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane graph; light graph; face size},
language = {eng},
number = {3},
pages = {403-411},
title = {On the structure of plane graphs of minimum face size 5},
url = {http://eudml.org/doc/270681},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Tomás Madaras
TI - On the structure of plane graphs of minimum face size 5
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 403
EP - 411
AB - A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star $K_{1,3}$ and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.
LA - eng
KW - plane graph; light graph; face size
UR - http://eudml.org/doc/270681
ER -

References

top
  1. [1] H. Enomoto and K. Ota, Connected Subgraphs with Small Degree Sums in 3-Connected Planar Graphs, J. Graph Theory 30 (1999) 191-203, doi: 10.1002/(SICI)1097-0118(199903)30:3<191::AID-JGT4>3.0.CO;2-X Zbl0916.05020
  2. [2] I. Fabrici, On vertex-degree restricted subgraphs in polyhedral graphs, Discrete Math. 256 (2002) 105-114, doi: 10.1016/S0012-365X(01)00368-5. Zbl1007.05063
  3. [3] I. Fabrici, J. Harant and S. Jendrol', Paths of low weight in planar graphs, submitted. Zbl1155.05010
  4. [4] I. Fabrici, E. Hexel, S. Jendrol' and H. Walther, On vertex-degree restricted paths in polyhedral graphs, Discrete Math. 212 (2000) 61-73, doi: 10.1016/S0012-365X(99)00209-5. Zbl0946.05047
  5. [5] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combin. 13 (1997) 245-250. Zbl0891.05025
  6. [6] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar graphs, Discrete Math. 191 (1998) 83-90, doi: 10.1016/S0012-365X(98)00095-8. Zbl0956.05059
  7. [7] J. Harant, S. Jendrol' and M. Tkáč, On 3-connected plane graphs without triangular faces, J. Combin. Theory (B) 77 (1999) 150-161, doi: 10.1006/jctb.1999.1918. Zbl1027.05030
  8. [8] S. Jendrol', T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467. Zbl0936.05065
  9. [9] S. Jendrol' and P. Owens, On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs and Combin. 17 (2001) 659-680, doi: 10.1007/s003730170007. Zbl0988.05031
  10. [10] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 111-113. 
  11. [11] H. Lebesgue, Quelques consequences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43. Zbl0024.28701
  12. [12] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. Zbl35.0511.01

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.