Minimum Size of Graphs Satisfying Ore Condition

HAO Chen, YANG Weihua

(1. School of Electronic Information Engineering, Jinzhong Vocational & Technical College,Jinzhong 030600, Shanxi China; 2. Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China)

Abstract：Determining the extremal graph under a given parameter is a classic topic in extremal graph theory. We determine the minimum size of graphs satisfying Ore condition and obtain a partial result for the minimum size of graphs satisfying Ore-type condition

Key words：Ore condition;extremal graph;minimum size of graphs

1 Extremal Graphs Satisfying Ore Condition

The graphs considered here are simply undirected. For a graphG, we useV(G),E(G) for its vertex set and edge set, respectively. In particular, we call |V(G)|, |E(G)| the order and the size of the graph. We follow Bondy et al[1-2]for terminologies not given here.

(1)

(2)

For the even number case, one can see that ifG∈On, then |E(G)|=exnif and only ifGis an 2-regular graph. We now consider the odd numbern. Combining the argument above, only two cases need to be discussed.

a contradiction.

Assume thattis odd.By ineq. (2), we have

(4)