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 \leq m \leq g\)) such that for any \(m\) consecutively adjacent vertices \(x_i\) (\(i = 1, 2, \ldots, m\)) in any non-chord cycle \(C\) of \(G\), it holds that

\[\sum\limits_{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.