Edge Maximal Non-Bipartite Graphs Without Odd Cycles of Prescribed Lengths |
| |
Authors: | Louis Caccetta Rui-Zhong Jia |
| |
Institution: | (1) School of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, 6845 Western Australia. e-mail: caccetta@cs.curtin.edu.au, AU |
| |
Abstract: | Let ?(n;3,5,…,2k+1) denote the class of non-bipartite graphs on n vertices having no odd cycle of length ≤2k+1. We prove that for every G∈?(n;3,5,…,2k+1) and characterize the extremal graphs. We also study the subclass ℋ(n;3,5,…,2k+1) consisting of the hamiltonian members of ?(n;3,5,…, 2k+1). For this subclass the above upper bound holds for odd n. For even n we establish the following sharp upper bound:
and characterize the extremal graphs.
Received: February 28, 1997 Final version received: August 31, 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|