- Title
- On the non-existence of even degree graphs of diameter 2 and defect 2
- Creator
- Miller; Mirka; Nguyen, Minh Hoang; Pineda-Villavicencio, Guillermo
- Date
- 2007
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/42847
- Identifier
- vital:3568
- Abstract
- Using eigenvalue analysis, it was shown by Erdos et al. that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d2-1 vertices do not exist for most values of d, when d is even, and we conjecture that they do not exist for any even d greater than 4.
- Publisher
- Rafferty's Resort, Lake Macquarie, New South Wales :
- Relation
- Paper presented at 18th International Workshop on Combinatorial Algorithms, IWOCA 2007, Rafferty's Resort, Lake Macquarie, New South Wales : 5th-9th November 2007
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0802 Computation Theory and Mathematics; Moore graphs; Diameter 2; Degree / diameter problem
- Full Text
- Hits: 928
- Visitors: 1058
- Downloads: 131
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Conference paper | 134 KB | Adobe Acrobat PDF | View Details Download |