Upper Embeddable Graphs Via the Degree-Sum of Adjacent Vertices

Abstract

A semi-double graph is such a connected multi-graph that each multi-edge consists of two edges. If there is at most one loop at each vertex of a semi-double graph, then this graph is called a single-petal graph. In this paper, we obtained that if $G$ is a connected (resp. $2$-edge-connected, $3$-edge-connected) simple graph of order $n$, then $G$ is upper embeddable if $d_G(u)+d_G(v)\ge \lceil \frac{2n-3}{2}\rceil$ (resp. $d_G(u)+d_G(v)\ge \lceil \frac{2n-2}{3}\rceil ,d_G(u)+d_G(v)\ge \lceil \frac{2n-23}{2}\rceil$) for any two adjacent vertices $u$ and $v$ of $G$. In addition, by means of semi-double graph and single-petal graph, the upper embeddability of multi-graph and pseudograph are also discussed in this paper.