Minimum Size of Graphs Satisfying Ore Condition
2019-11-19HAOChenYANGWeihua
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)