Back to search
University of British Columbia
Going critical : an investigation of diameter -critical graphs
Abstract
dc:descriptionWe define a graph G=(V, E) with m=\E\ edges, n=\V\ vertices, maximum degree D, and diameter d, to be d-critical if it has the property that for any edge e G E, the graph G — e has diameter > d. We explore some results relating to a conjecture on the maximum possible number of edges in a 2-critical graph. We also present efficient algorithms for identifying spanning d-critical subgraphs of graphs having diameter d where d=2 or d=3. The algorithm for d=2 runs in 0(mn), and the algorithm for d=3 runs in 0(mnD).
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Mathematics
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 1999
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Madden, Joshua
Rights
dc:rights- Statement dc:rights
-
- For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/10030