Abstract
The Shields-Harary number (SH) is a graph parameter which has been interpreted in terms of network vulnerability. There is no known algorithm for calculating SH. In this paper, we study the Shields-Harary number for wheel graphs and wheel graphs with deleted outer edges. Wheels with sufficiently many outer edges deleted have the same value of SH as the star. Wheels and wheels with too few edges deleted have a different (but very close) value of SH, which is not precisely known. We show that infinitely many of these graphs have non-integral values of SH. Formerly, only one such graph was known.
Original language | English (US) |
---|---|
Pages (from-to) | 193-199 |
Number of pages | 7 |
Journal | Discrete Applied Mathematics |
Volume | 59 |
Issue number | 2 |
DOIs | |
State | Published - May 12 1995 |
Funding
The author would like to thank Prof. P. D. Johnson, Prof. Joseph Gallian, David Moulton, and Mike Reid for their help in researchinga nd writing this paper.T he refereec ontributeda n importantc orrectiont o Proposition 2 in addition to many helpful suggestionsT.h e work was done at the University of Minnesota,D uluth, with support from Prof. Gallian’s NSF grant DMS-9000742a nd his NSA grant MDA904-91-0036.
Keywords
- Broken wheels
- Networks
- Shields-Harary number
- Wheels
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics