The Degree-Sum of Adjacent Vertices, Girth and Upper Embeddability

Abstract

This paper investigates the relationship between the degree-sum of adjacent vertices, girth, and upper embeddability of graphs, combining it with edge-connectivity. The main result is:
Let $G$ be a $k$-edge-connected simple graph with girth $g$. If there exists an integer $m$ ($1\le m\le g$) such that for any $m$ consecutively adjacent vertices $x_i$ ($i=1,2,\dots ,m$) in any non-chord cycle $C$ of $G$, it holds that

$$\sum _{i=1}^m{d}_G(x_i)>\frac{mn}{(k-1{)}^2+2}+\frac{km}{g}+(2-g)m,$$

where $k=1,2,3,n=|V(G)|$, then $G$ is upper embeddable and the upper bound is best possible.