Displaying 961 – 980 of 1226

Showing per page

An Extension of Kotzig’s Theorem

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

Discussiones Mathematicae Graph Theory

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 in which every...

Currently displaying 961 – 980 of 1226