On light cycles in plane triangulations.

*(English)*Zbl 0936.05065A graph \(H\) is said to be light in the class of graphs \({\mathcal G}\) if there exists a positive integer \(k\) such that each graph \(G\in{\mathcal G}\) that contains an isomorphic copy of \(H\) contains a subgraph \(K\) isomorphic to \(H\) that satisfies the inequality \(\deg_G(v)\leq k\), for all vertices \(v\) of \(K\). The smallest positive integer \(k\) with this property is denoted by \(\varphi(H,{\mathcal G})\).

In the main result of the paper, the authors present a complete classification of cycles \(C_r\) that are light in the class \({\mathcal T}(5)\) of plane triangulations with minimum degree 5, namely, they show that a cycle \(C_r\) is light in \({\mathcal T}(5)\) if and only if \(r\in\{3, 4, 5, 6, 7, 8, 9, 10\}\). As for the numbers \(\varphi(C_r,{\mathcal T}(5))\), they show that \(10\leq \varphi(C_6,{\mathcal T}(5))\leq 11\), \(15\leq\varphi(C_7,{\mathcal T}(5))\leq 17\), \(15\leq \varphi(C_8,{\mathcal T}(5))\leq 29\), \(19\leq \varphi(C_9,{\mathcal T}(5))\leq 41\), \(20\leq \varphi(C_{10},{\mathcal T}(5))\leq 415\) (the remaining three identities are \(\varphi(C_3,{\mathcal T}(5))= 7\), \(\varphi(C_4,{\mathcal T}(5))= 10\), \(\varphi(C_5,{\mathcal T}(5))= 10\); the last two have been shown by S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207-217 (1996; Zbl 0877.05050)]; \(C_{10}\) has been shown to be light in \({\mathcal T}(5)\) by T. Madaras ans R. Soták).

Most of the paper is devoted to proving the theorem. The proofs of the fact that none of the \(C_r\)’s with \(r>10\) is light in \({\mathcal T}(5)\) and of the lower bounds are constructive. The upper bounds are the result of a clever application of a “discharge method” to the hypothetical counterexamples.

In the main result of the paper, the authors present a complete classification of cycles \(C_r\) that are light in the class \({\mathcal T}(5)\) of plane triangulations with minimum degree 5, namely, they show that a cycle \(C_r\) is light in \({\mathcal T}(5)\) if and only if \(r\in\{3, 4, 5, 6, 7, 8, 9, 10\}\). As for the numbers \(\varphi(C_r,{\mathcal T}(5))\), they show that \(10\leq \varphi(C_6,{\mathcal T}(5))\leq 11\), \(15\leq\varphi(C_7,{\mathcal T}(5))\leq 17\), \(15\leq \varphi(C_8,{\mathcal T}(5))\leq 29\), \(19\leq \varphi(C_9,{\mathcal T}(5))\leq 41\), \(20\leq \varphi(C_{10},{\mathcal T}(5))\leq 415\) (the remaining three identities are \(\varphi(C_3,{\mathcal T}(5))= 7\), \(\varphi(C_4,{\mathcal T}(5))= 10\), \(\varphi(C_5,{\mathcal T}(5))= 10\); the last two have been shown by S. Jendrol’ and T. Madaras [Discuss. Math., Graph Theory 16, No. 2, 207-217 (1996; Zbl 0877.05050)]; \(C_{10}\) has been shown to be light in \({\mathcal T}(5)\) by T. Madaras ans R. Soták).

Most of the paper is devoted to proving the theorem. The proofs of the fact that none of the \(C_r\)’s with \(r>10\) is light in \({\mathcal T}(5)\) and of the lower bounds are constructive. The upper bounds are the result of a clever application of a “discharge method” to the hypothetical counterexamples.

Reviewer: R.Jajcay (Terre Haute)

PDF
BibTeX
XML
Cite

\textit{S. Jendrol'} et al., Discrete Math. 197--198, 453--467 (1999; Zbl 0936.05065)

Full Text:
DOI

##### References:

[1] | Ando, K.; Iwasaki, S.; Kaneko, A., Every 3-connected planar graph has a connected subgraph with small degree sum, (), (in Japanese) |

[2] | Borodin, O.V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Mat. zametki, 46, 5, 9-12, (1989) · Zbl 0694.05027 |

[3] | Borodin, O.V., On the total coloring of plane graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029 |

[4] | Borodin, O.V., Triangles with restricted degree sum of their boundary vertices in plane graphs, Discrete math., 137, 45-51, (1995) · Zbl 0814.05030 |

[5] | Borodin, O.V., Minimal vertex degree sum of a 3-path in plane maps, Discuss. math. graph theory, 17, 279-284, (1997) · Zbl 0906.05017 |

[6] | Borodin, O.V.; Sanders, D.P., On light edges and triangles in planar graphs of minimum degree five, Math. nachr., 170, 19-24, (1994) · Zbl 0813.05020 |

[7] | O.V. Borodin, D.R. Woodall, Short cycles of low weight in normal plane maps with minimum degree, Discuss. Math. Graph Theory, to appear. · Zbl 0927.05069 |

[8] | Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs combin., 13, 245-250, (1997) · Zbl 0891.05025 |

[9] | I. Fabrici, E. Hexel, S. Jendrol’, H. Walther, On vertex-degree restricted paths in polyhedral graphs, Discrete Math., submitted. · Zbl 0946.05047 |

[10] | Franklin, P., The four colour problem, (), 44, 1737-1936, (1922), or in |

[11] | Grünbaum, B., New views on some old questions of combinatorial geometry, (), 451-468 |

[12] | Grünbaum, B., Polytopal graphs, MAA studies math., vol. 12, 201-224, (1975) · Zbl 0323.05104 |

[13] | S. Jendrol’, Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J., to appear. · Zbl 1003.05055 |

[14] | Jendrol’, S.; Madaras, T., On light subgraphs in plane graphs of minimum degree five, Discuss. math. graph theory, 16, 207-217, (1996) · Zbl 0877.05050 |

[15] | Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat.-fyz. čas. SAV (math. slovaca), 5, 111-113, (1955), (in Slovak) |

[16] | Kotzig, A., On the theory of Euler’s polyhedra, Mat.-fyz. čas. SAV (math. slovaca), 13, 20-31, (1963), (in Russian) · Zbl 0134.19601 |

[17] | Lebesgue, H., Quelques consequences simples de la formule d’Euler, J. math. pures appl., 19, 19-43, (1940) · JFM 66.0736.03 |

[18] | T. Madaras, R. Soták, The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra Mt. Math. Publ., to appear. |

[19] | Wernicke, P., Über den kartographischen vierfarbensatz, Math. ann., 58, 413-426, (1904) · JFM 35.0511.01 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.