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

O.V. Borodin

The search session has expired. Please query the service again.

Displaying similar documents to “Minimal vertex degree sum of a 3-path in plane maps”

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

Oleg V. Borodin, Anna O. Ivanova, Tommy R. Jensen (2014)

Discussiones Mathematicae Graph Theory

Similarity:

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

Near-homogeneous spherical Latin bitrades

Nicholas J. Cavenagh (2013)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A planar Eulerian triangulation is a simple plane graph in which each face is a triangle and each vertex has even degree. Such objects are known to be equivalent to spherical Latin bitrades. (A Latin bitrade describes the difference between two Latin squares of the same order.) We give a classification in the near-regular case when each vertex is of degree $4$ or $6$ (which we call a near-homogeneous spherical Latin bitrade, or NHSLB). The classification demonstrates that any NHSLB is equal...

Note on the weight of paths in plane triangulations of minimum degree 4 and 5

Tomás Madaras (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The weight of a path in a graph is defined to be the sum of degrees of its vertices in entire graph. It is proved that each plane triangulation of minimum degree 5 contains a path P₅ on 5 vertices of weight at most 29, the bound being precise, and each plane triangulation of minimum degree 4 contains a path P₄ on 4 vertices of weight at most 31.

Distance in graphs

Roger C. Entringer, Douglas E. Jackson, D. A. Snyder (1976)

Czechoslovak Mathematical Journal

Similarity:

On bounded paradoxical subsets of the plane

Glen Sherman (1990)

Fundamenta Mathematicae

Similarity:

A new upper bound on the total domination number of a graph.

Henning, Michael A., Yeo, Anders (2007)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

An Extension of Kotzig’s Theorem

Valerii A. Aksenov, Oleg V. Borodin, Anna O. Ivanova (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2...