The structure of graphs with given lengths of cycles |
| |
Institution: | 1. School of Mathematical Sciences, East China Normal University, 500 Dongchuan Road, Shanghai 200240, China;2. School of Mathematical Sciences and Shanghai Key Laboratory of PMMP, East China Normal University, 500 Dongchuan Road, Shanghai 200240, China |
| |
Abstract: | The cycle spectrum of a given graph G is the lengths of cycles in G. In this paper, we introduce the following problem: determining the maximum number of edges of an n-vertex graph with given cycle spectrum. In particular, we determine the maximum number of edges of an n-vertex graph without containing cycles of lengths three and at least k. This can be viewed as an extension of a well-known result of Erd?s and Gallai concerning the maximum number of edges of an n-vertex graph without containing cycles of lengths at least k. We also determine the maximum number of edges of an n-vertex graph whose cycle spectrum is a subset of two positive integers. |
| |
Keywords: | Cycle spectrum Erd?s and Gallai Theorem |
本文献已被 ScienceDirect 等数据库收录! |
|