- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Going critical : an investigation of diameter -critical...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Going critical : an investigation of diameter -critical graphs Madden, Joshua
Abstract
We 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).
Item Metadata
| Title |
Going critical : an investigation of diameter -critical graphs
|
| Creator | |
| Publisher |
University of British Columbia
|
| Date Issued |
1999
|
| Description |
We 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).
|
| Extent |
2673799 bytes
|
| Genre | |
| Type | |
| File Format |
application/pdf
|
| Language |
eng
|
| Date Available |
2009-07-03
|
| Provider |
Vancouver : University of British Columbia Library
|
| 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.
|
| DOI |
10.14288/1.0080060
|
| URI | |
| Degree | |
| Program | |
| Affiliation | |
| Degree Grantor |
University of British Columbia
|
| Graduation Date |
1999-05
|
| Campus | |
| Scholarly Level |
Graduate
|
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
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.