- Title
- Construction of extremal graphs
- Creator
- Tang, Jianmin; Lin, Yuqing; Miller, Mirka
- Relation
- 19th International Workshop on Combinatorial Algorithms (IWOCA 2008). IWOCA 2008: Proceedings of 19th International Workshop on Combinatorial Algorithms (Nagoya, Japan 12-15 September, 2008) p. 42-49
- Relation
- http://www.iwoca.org/iwoca2008/default.htm
- Publisher
- IWOCA 2008
- Resource Type
- conference paper
- Date
- 2008
- Description
- By extremal number ex(n;t ) = ex(n;{C₃, C₄, ..., Ct}) we denote the maximum size (that is, number of edges) in a graph of order n and girth at least g ≥ t + 1. The set of all graphs of order n, containing no cycle of length ≤ t, and of size ex(n:t), is denoted by EX(n;t) = EX(n;{C₃, C₄, ..., Ct}); such graphs are called extremal graphs. In 1975. Erdës mentioned the problem of determining the extremal number 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. We also improve upper bounds of exu(n;t), for some particular values of n and t. Furthermore, we generate graphs in which the number of edges improves the current lower bounds of ex(n;6) when n ≤ 40.
- Subject
- extremal graph; extremal number; cages
- Identifier
- uon:5919
- Identifier
- http://hdl.handle.net/1959.13/44930
- Reviewed
- Hits: 1475
- Visitors: 1747
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|