๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Extending two theorems of A. Kotzig

โœ Scribed by Joseph Zaks

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
585 KB
Volume
43
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Two theorems of A. Kotzig are extended, as follows:

(1) A. Kotzig proved in 1963 that every 5-valent Sconnected planar graph contains a vertex which meets at least four triangles. We prove that if a 5-valent 3-connected graph on the orientable surface of genus g has pk k-gons, k 33, and mi vertices meeting precisely i triangles, OCiG5, then nt,+2m,~24(l-g)+3C,,,(k_4)pk; as a corollary we get rn5a 12(1-g)+Ck;ad (k -6)pk.

(2) Let a(e) denote the sum of the valences of the two faces incident with the edge e of a planar graph. A. Kotzig proved that every 4-valent 3-connected planar graph has an edge e such that 8(e)<'. We use Kotzig's proof to get the bound 9 in the corresponding toroidal case.

๐Ÿ“œ SIMILAR VOLUMES

Two recursive theorems on n-extendibilit
Two recursive theorems on n-extendibility
โœ Tsuyoshi Nishimura; Akira Saito ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 255 KB

We give two recursive theorems on n-extendible graphs. A graph G is said to be (k,n)extendible if every connected induced subgraph of G of order 2k is n-extendible. It is said to be [k, hi-extendible if G -V(H) is n-extendible for every connected induced subgraph H of G of order 2k. In this note we