- Title
- New results on EX graphs
- Creator
- Tang, Jianmin; Lin, Yuqing; Miller, Mirka
- Relation
- Mathematics in Computer Science Vol. 3, Issue 1, p. 119-126
- Publisher Link
- http://dx.doi.org/10.1007/s11786-009-0009-6
- Publisher
- Birkhauser
- Resource Type
- journal article
- Date
- 2010
- Description
- By the extremal number ex(n; t) = ex(n; {C₃,C₄, . . . ,Cᵼ }) we denote the maximum size (that is, number of edges) in a graph of order n > t and girth at least g ≥ t + 1. The set of all the graphs of order n, containing no cycles of length ≤ t, and of size ex(n; t), is denoted by EX(n; t) = EX(n; {C₃,C₄, . . . ,Cᵼ }), these graphs are called EX graphs. In 1975, Erdős proposed the problem of determining the extremal numbers ex(n; 4) of a graph of order n and girth at least 5. In this paper, we consider a generalized version of this problem, for t ≥ 5. In particular, we prove that ex(29; 6) = 45, also we improve some lower bounds and upper bounds of exᴜ(n; t), for some particular values of n and t.
- Subject
- EX graph; extremal number; cages; Erdős
- Identifier
- http://hdl.handle.net/1959.13/932199
- Identifier
- uon:11283
- Identifier
- ISSN:1661-8270
- Language
- eng
- Reviewed
- Hits: 1921
- Visitors: 1893
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|