ArticleOriginal scientific text

Title

Minimal vertex degree sum of a 3-path in plane maps

Authors 1

Affiliations

  1. Novosibirsk State University

Abstract

Let wₖ be the minimum degree sum of a path on k vertices in a graph. We prove for normal plane maps that: (1) if w₂ = 6, then w₃ may be arbitrarily big, (2) if w₂ < 6, then either w₃ ≤ 18 or there is a ≤ 15-vertex adjacent to two 3-vertices, and (3) if w₂ < 7, then w₃ ≤ 17.

Keywords

planar graph, structure, degree, path, weight

Bibliography

  1. O.V. Borodin, Solution of Kotzig's and Grünbaum's problems on the separability of a cycle in plane graph, (in Russian), Matem. zametki 48 (6) (1989) 9-12.
  2. O.V. Borodin, Triangulated 3-polytopes without faces of low weight, submitted.
  3. H. Enomoto and K. Ota, Properties of 3-connected graphs, preprint (April 21, 1994).
  4. K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum I, II (in Japanese), Annual Meeting of Mathematical Society of Japan, 1993.
  5. Ph. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236, doi: 10.2307/2370527.
  6. S. Jendrol', Paths with restricted degrees of their vertices in planar graphs, submitted.
  7. S. Jendrol', A structural property of 3-connected planar graphs, submitted.
  8. A. Kotzig, Contribution to the theory of Eulerian polyhedra, (in Russian), Mat. Čas. 5 (1955) 101-103.
Pages:
279-284
Main language of publication
English
Received
1996-04-23
Accepted
1997-03-04
Published
1997
Exact and natural sciences