The Shields-Harary Number of Graphs
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee.
John Edwin Holliday
Certi cate of Approval:
Dr. Kevin T. Phelps
Professor
Discrete and Statistical Sciences
Dr. Peter D. Johnson Jr., Chair
Professor
Discrete and Statistical Sciences
Dr. Dean G. Ho man
Professor
Discrete and Statistical Sciences
Dr. Overtoun Jenda
Professor
Discrete and Statistical Sciences
Stephen McFarland
Dean
Graduate School
The Shields-Harary Number of Graphs
John Edwin Holliday
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Ful llment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
May 14, 2004
Vita
John Edwin Holliday was born on September 10, 1971 in Miami, Florida, the third
of six children of Alvin Fletcher and Janice Holliday.
He attended Habersham Central High School in Mt. Airy, Georgia and graduated
with honors in 1989. He then attended Truett-McConnell Junior College in Cleveland,
Georgia, where he was listed in Who?s Who Among American Junior College Students.
He graduated Magna Cum Laude in 1992 with an Associate?s Degree in Music, special-
izing in trombone performance.
He later attended Jacksonville State University in Jacksonville, Alabama, where he
received the Outstanding Undergraduate Mathematics Student Award in the Spring of
1997 and graduated Magna Cum Laude with a Bachelor of Science in Mathematics and
in Computer Science on May 8, 1997. He immediately began his studies at Auburn
University?s Department of Discrete and Statistical Sciences and recieved the Master of
Applied Mathematics degree on March 18, 2000.
He is married to Sarah Hale-Heuss Holliday and has one son, Kolby Tyler Holliday.
iii
Dissertation Abstract
The Shields-Harary Number of Graphs
John Edwin Holliday
Doctor of Philosophy, May 14, 2004
(M.A.M., Auburn University, June 10, 2000)
(B.S., Jacksonville State University, May 8, 1997)
55 Typed Pages
Directed by Dr. Peter D. Johnson, Jr.
The Shields-Harary numbers are a class of graph paramaters that measure the ro-
bustness of a graph in terms of network vulnerability, with reference to a given cost
function.
iv
Style manual or journal used Discrete Mathematics (together with the style known
as \auphd"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speci cally
LATEX2") together with the departmental style- le auphd.sty.
v
Table of Contents
List of Figures vii
1 The Shields-Harary Numbers 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 An example of the Shields-Harary Numbers . . . . . . . . . . . . . . . . . 3
1.4 The History of the Shields-Harary Numbers and a Review of Literature. . 8
2 The Shields-Harary Number of Kn e 13
2.1 Full Solution of Kn e with optimal weighting possibilities . . . . . . . . 13
2.2 Examples of di erent cost functions for each Mi . . . . . . . . . . . . . . . 18
2.3 A counterexample to the constant weights on orbits conjecture . . . . . . 19
3 Some General Results with Applications to Intersecting Cliques 23
3.1 A useful proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Limits of Optimal Weightings . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 An application of Proposition 3.3 and other useful results . . . . . . . . . 30
4 The Shields-Harary Numbers of Km;n for Some Cost Functions 34
4.1 Some generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 The constant-on-each-part Shields-Harary numbers of Km;n . . . . . . . . 46
Bibliography 48
vi
List of Figures
1.1 Our graph G with weighting g1 . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Dismantling (G,g1) by disconnecting . . . . . . . . . . . . . . . . . . . . . 4
1.3 Dismantling but not disconnecting . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Graph G with weighting g2 . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Dismantling G with weighting g2 by disconnecting. . . . . . . . . . . . . . 6
1.6 Dismantling G with weighting g2 but not disconnecting. . . . . . . . . . . 6
1.7 G with constant weighting g3. . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.8 Cheapest dismantling of G with weighting g3. . . . . . . . . . . . . . . . . 7
2.1 Kn e with constant on orbits weighting g . . . . . . . . . . . . . . . . . 20
3.1 G(l;r;s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 G(3;3;1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
vii
Chapter 1
The Shields-Harary Numbers
1.1 Introduction
Suppose we have a simple, nite non-empty graph G = (V;E) whose vertices have
non-negative weights g(v), v 2 V where g : V ! [0;1). We can consider this graph to
be some network where the weight at each vertex represents some amount of harmful
material stored at that particular location (vertex).
This network has an enemy who wishes to dismantle it by removing vertices from the
network and thus destroying the material stored at the removed vertices. The network
is considered dismantled when the sum of the weights on each remaining connected
component of the network after vertex removal is less than or equal to some threshold,
say 1. The defense that the network has against the enemy is that it costs the enemy
a certain price to remove these vertices. The enemy pays f(g(v)) to remove v 2 V
and
X
v2S
f(g(v)) to remove a set S of vertices where f is some decreasing (or at least
non-increasing) cost function on the range of g.
We will assume that the enemy is intelligent and has complete knowledge of the
weighted network and so for any allocation of weights throughout the network, the
enemy will always choose to remove the set of vertices that dismantles the network while
giving rise to the least possible total cost. This least possible total cost that the enemy
pays for a particular weighting g shall be denoted by mf(g;G). We endeavor to make the
enemy pay as much as possible. In section [1.2], we de ne things a little more precisely,
as well as de ning what the Shields-Harary numbers are.
1
2
1.2 De nitions
Let G = (V;E), S V , g : V ! [0;1) and let f be some non-increasing cost
function on the range of g.
Why is the cost function f decreasing (or at least non-increasing)? The idea is that
the more harmful material you have stored in one location, the harder it will be to defend
and thus it will be easier (cheaper) for the enemy to remove from the network.
We call S a g-dismantling set if and only if
X
v2V (H)
g(v) 1 for each component H
of G S. The Shields-Harary number of a graph G with respect to the cost function f
is given by
SH(G;f) = sup
g:V![0;1)
mf(g;G).
Recall that mf(g;G) is the least possible cost to dismantle the graph G with the speci c
weighting g.
Now suppose we change the de nition of dismantling so that the network is disman-
tled when the sums of the weights on each remaining connected component is strictly
less than 1. We call S a strict g-dismantling set if and only if
X
v2V (H)
g(v) < 1 for each
component H of G S. The least possible cost to strictly dismantle the graph G with
weighting g is denoted by mf(g;G). We denote the Shields-Harary number of a graph
with this de nition of dismantling by
SH(G;f) = sup
g:V![0;1)
mf(g;G).
We de ne SH0(G;f) and SH0(G;f) in the same manner as above except that our
weighting functions are restricted to be constant. It is elementary that in the de nitions
of SH and SH0, the weighting functions may as well be into [0;1].
3
In [2] it was shown that if f is continuous from the right at each point of [0;1]
then the \sup" in the de nition of SH(G;f) is always a maximum (i.e. we can actually
make the enemy pay this amount). A weighting g which yields this \max" will be called
optimal (for G and f).
1.3 An example of the Shields-Harary Numbers
Having now de ned all of the terms that we need, (for any others, refer to [9]), let
us now illustrate the concept of the Shields Harary Numbers (SH numbers for short)
by looking at an example of how the SH number relates to a graph with a particular
weighting and cost function. In later chapters, we will further explore the intricacies of
these calculations by actually calculating the SH numbers of speci c graphs with respect
to various cost functions.
Consider the following graph G with the cost function f(x) = 1x and weighting g1
as illustrated by Figure 1.1.
a0
a0a1
a1
a2
a2a3
a3
a4
a4a5
a5
a6
a6a7
a7
a8
a8a9
a9
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a10a11a10a11a10a11a10
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a12a11a12a11a12a11a12
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a13a11a13a11a13a11a13
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a14a11a14a11a14a11a14
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a15a11a15a11a15a11a15a11a15
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a16a11a16a11a16a11a16
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a17a11a17a11a17a11a17
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
a18a11a18a11a18a11a18
5
8
4
8
2
8
1
8
3
8
Figure 1.1: Our graph G with weighting g1
4
The enemy whose intelligence is poor might yield to the temptation of dismantling
this graph by removing the central vertex of weight 18; thus disconnecting the graph
with the resulting components shown in Figure 1.2. This dismantling would yield a
dismantling cost of f(18) = 8. At a quick glance, this might seem a logical choice since
the enemy would only have to remove a single vertex. Better intelligence, however, would
make it clear that the enemy could more cheaply dismantle this graph by removing the
two vertices of weights 58 and 48 with the resulting component shown in Figure 1.3. This
dismantling yields a dismantling cost of f( 58) + f(48) = 85 + 84 = 185 < 8. So dismantling
does not always imply disconnecting the graph. Notice that in both cases, the sum of
the weights on each remaining component of the graph is strictly less than one and so
the enemy in this example would pay 185 as this is the cheapest dismantling cost for
this particular weighting. Without considering any other weightings, we would say that
SH(G; 1x) 185 .
a19
a19a20
a20
a21
a21a22
a22
a23
a23a24
a24
a25
a25a26
a26
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a27a11a27a11a27a11a27
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a28a11a28a11a28a11a28
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a29a11a29a11a29a11a29
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
a30a11a30a11a30a11a30
5
8
4
8
2
8
3
8
Figure 1.2: Dismantling (G,g1) by disconnecting
5
a31
a31a32
a32
a33
a33a34
a34
a35
a35a36
a36
2
8
1
8
3
8
Figure 1.3: Dismantling but not disconnecting
Let us now consider some other weightings of G. Suppose we consider the following
weighting of G:
a37
a37a38
a38
a39
a39a40
a40
a41
a41a42
a42
a43
a43a44
a44
a45
a45a46
a46
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a47a11a47a11a47a11a47
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a48a11a48a11a48a11a48
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a49a11a49a11a49a11a49
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a50a11a50a11a50a11a50
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a51a11a51a11a51a11a51a11a51
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a52a11a52a11a52a11a52
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a53a11a53a11a53a11a53
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
a54a11a54a11a54a11a54
3
7
3
7
1
7
3
7
3
7
Figure 1.4: Graph G with weighting g2
There are two ways in which we can dismantle G with this particular weighting.
One way would be to remove the central vertex of weight 17 and pay a cost of f(17) = 7.
This dismantling leaves the components as shown in Figure 1.5. The other way in which
we could dismantle this graph would be to use a greedy algorithm and keep removing
the vertex of the largest weight until the graph is dismantled. With strict dismantling
in mind, we are required to remove three of the vertices of weight 37 which gives rise to a
removal cost of 3f(37) = 3(73) = 7 and is illustrated in Figure 1.6. (As one can see, unlike
6
the rst weighting, with this weighting we get the same cost whether we disconnect the
graph or not.) So SH(G; 1x) 7 > 185 .
a55
a55a56
a56
a57
a57a58
a58
a59
a59a60
a60
a61
a61a62
a62
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a63a11a63a11a63a11a63
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a64a11a64a11a64a11a64
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a65a11a65a11a65a11a65
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
a66a11a66a11a66a11a66
3
7
3
7
3
7
3
7
Figure 1.5: Dismantling G with weighting g2 by disconnecting.
a67
a67a68
a68
a69
a69a70
a70
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a71a11a71a11a71a11a71a11a71
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
a72a11a72a11a72a11a72a11a72
3
7
1
7
Figure 1.6: Dismantling G with weighting g2 but not disconnecting.
Let us now consider a constant weighting of our graph G as shown in Figure 1.7.
With this particular weighting and with strict dismantling in mind, we cannot leave two
adjacent vertices. In this situation, we want to remove the fewest number of vertices
that we can and so the structure of the graph comes into play. If we leave the center
vertex in, then we must remove the four outer vertices. However, we can get away
7
with only removing three as shown in Figure 1.8. This dismantling forces us to pay
3f(12) = 3(2) = 6. Thus it remains that, SH(G; 1x) 7 > 6. However, we nd also that
SH0(G) 6. (By results to be introduced later, it will be easy to see that SH0(G) = 6.)
a73
a73a74
a74
a75
a75a76
a76
a77
a77a78
a78
a79
a79a80
a80
a81
a81a82
a82
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a83a11a83a11a83a11a83
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a84a11a84a11a84a11a84
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a85a11a85a11a85a11a85
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a86a11a86a11a86a11a86
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a87a11a87a11a87a11a87a11a87
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a88a11a88a11a88a11a88
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a89a11a89a11a89a11a89
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
a90a11a90a11a90a11a90
1
2
1
2
1
2
1
2
1
2
Figure 1.7: G with constant weighting g3.
a91
a91a92
a92
a93
a93a94
a94
1
2
1
2
Figure 1.8: Cheapest dismantling of G with weighting g3.
From these di erent weightings, one can see that the computation of SH G; 1x is
not necessarily a trivial calculation. In fact, the problem of computing SH G; 1x is
indeed a ve variable optimization problem.
8
1.4 The History of the Shields-Harary Numbers and a Review of Literature.
The Shields-Harary numbers arose from a conjecture of the late Allen Shields. In
1972, at a University of Michigan Math Club meeting, Shields posed the following con-
jecture:
For any sequence of positive numbers d1;d2;::: ;dn there exists a set S
f1;2;::: ;ng such that
X
i2S
1
di n and for each set of consecutive integers
(block) B of f1;::: ;ngn S,
X
i2B
di 1.
In terms of graph theory, Shields? conjecture was actually that SH(Pn;f) n where
Pn is the path on n vertices and f is the cost function f(x) = 1x.
Realizing that this conjecture was connected to graphs, Shields consulted Frank
Harary. They soon proved that if SH(Pn; 1x) = n, then SH(Cn; 1x) = 2n 2 where Cn is
the cycle of length n. They also computed the values of SH(Kn; 1x) and SH(K1;n 1; 1x).
Both of these values are around n24 , which is interesting; by this measure of network
robustness, stars are close to cliques and are much more robust than cycles. However,
Shields and Harary never did prove Shields? original conjecture. Instead, it was proven,
by a clever \cost analysis" argument, by Stephen Schanuel [7].
Initially, much of what was done with the Shields-Harary parameters dealt with
the speci c cost function f(x) = 1x, which was the cost function involved in Shields?
original conjecture. Johnson [6] presented everything known at the time about the SH
parameters with that particular cost function. Another paper by Wunsch [8], also on
the original Shields-Harary number, obtains an in nite number of graphs G for which
9
SH(G; 1x) is not an integer, through asymptotic estimates of SH(G) for G in a certain
family of graphs. (Johnson had found one graph for which SH(G) was not an integer.)
Some more recent work has dealt with the constant weight Shields-Harary numbers.
The basis for the work on the SH0 numbers is a result in [2] which reduces the com-
putation of SH0 or SH0 of a graph to computing the minimum cardinality of a set of
vertices whose removal from the graph leaves components of a certain size. This result
is as follows:
SH0(G;f) = max
1 k n
p(k;G)f
1
k
where p(k;G) is the minimum cardinality of a set S V (G) such that each component
of G S has k 1 or fewer vertices. In [5] it is shown that for all non-increasing cost
functions f and all trees T on n vertices, SH0(K1;n 1;f) SH0(T;f) SH0(Pn;f)
with the same inequality holding for SH0. In [5] the authors also show that for all
trees T on n vertices, 1 p(k;T)
jn
k
k
, 2 k n. Another paper, [1], shows that
SH(G;f) SH(G + e;f) for any edge e between non-adjacent vertices of G. This
inequality holds for SH, SH0 and SH0. This result proved useful in the calculations of
the values of SH0(G;f) in terms of p(k;G) when G is a special kind of Cayley Graph.
(See [1]).
The inequality SH(G;f) SH(G + e;f) mentioned above is a special case of the
monotonicity of the Shields-Harary numbers with respect to taking subgraphs. Surpris-
ingly, this monotonicity is not completely trivial; we prove it here.
Proposition 1.1 Suppose that P 2 fSH;SH;SH0;SH0g, with respect to some cost
function f, and that G1 is a subgraph of G. Then P(G1) P(G).
10
Proof. Suppose that > 0 and g is a weighting of V (G1) such that the minimum cost m
of (strictly) dismantling (G1;g) satis es P(G1) < m; and, of course, m P(G1). (If
P 2 fSH0;SH0g, g is a constant function.) In case V (G)nV (G1) is non-empty, extend g
to a weighting ~g on V (G) any which way; but ~g = g on V (G)nV (G1) if g is constant. We
shall prove that the minimum cost ~m of (strictly) dismantling (G; ~g) satis es ~m m. It
will then follow that P(G) P(G1) for all > 0, and thence the desired conclusion.
Let ~S be a ~g-dismantling set of vertices of minimum cost, say ~m and let S1 be the
set of vertices de ned as follows, S1 = ~S \V (G1). Now suppose that u;v 2 V (G1 S1)
such that u;v are in the same component of G1 S1. We can then nd a path in G1 S1
from u to v. Such a path will also be in G ~S since all of the edges and vertices of
G1 S1 are in G ~S as well, in view of the de nition of S1 and the fact that G1 is a
subgraph of G. Thus, any vertices of G1 that lie in the same component of G1 S1 must
lie in the same component of G ~S and so every component of G1 S1 is contained in
a component of G ~S.
Since the components of G1 S1 are subgraphs of the components of G ~S, it follows
that S1 dismantles G1. Since S1 is a subset of ~S, it follows that the cost of removing S1
is no more than ~m (the cost of removing ~S). Thus, the minimum dismantling cost m of
(G1;g) is such that m ~m.
A paper from Harary and Johnson [2] presents more results on the Shields-Harary
parameter, with arbitrary cost functions. Here are some of those results.
1. If f is a continuous function, then SH(G;f) = SH(G;f) and SH0(G;f) =
SH0(G;f). (Incidentally, f is allowed to take the value 1 and still be contin-
uous throughout.)
11
2. If f is continuous, then the sup in the de nition of SH(G;f) and SH0(G;f) is
always a max.
3. SH(Kn;f) = SH0(Kn;f) = max
1 k n
(n k +1) f
1
k
+
, where f
1
k
+
is the right
hand limit of f at 1k.
4. max
1 k n
jn
k
k
f
1
k
SH(Pn;f) n sup
0>>
>>>
><
>>>>
>>>:
(n 1)f(1 x) if f(0) > 2f(1), for some
x 2 (0; 12] s.t. f(x) = 2f(1 x)
M2 if f(0) 2f(1):
Proof. In the rst part of this proof, we will show that there is a weighting of Kn e
for each Mi, 1 i 3, so that the (strict) dismantling of Kn e costs Mi. This will
prove that SH(Kn e;f) max(M1;M2;M3). Let us denote the vertices of Kn by
v1;::: ;vn and let e = vn 1 vn.
Let us rst consider the constant weighting 1k;k 2 f1;3;4;::: ;ng on the vertices of
Kn e. When k = 1, we put a weight of 1 on all vertices. To dismantle, we must knock
out all of the vertices, at a cost of nf(1). When k > 2, we can dismantle the Kn e
13
14
by either removing the Kn 2 induced by v1;::: ;vn 2 or by leaving some vertices in the
Kn 2 and then knocking out vertices until the sum of the weights on the remaining
component is strictly less than one. If we remove the Kn 2, we do so at a cost of
(n 2) f(1k) (n k + 1) f( 1k). If we knock out vertices until the sum of weights is
less than 1, then we must knock out n (k 1) = (n k + 1) vertices at a cost of
(n k + 1) f( 1k). When k 3, this is the cheaper of the two dismantlings. Thus, for
each k 2 f1;3;::: ;ng, the dismantling cost is (n k + 1)f( 1k); therefore the cost M1 is
achieved by one of these weightings.
Now, consider the dismantling cost required by placing a weight of 1 on vn and a
weight of 12 on v1;::: ;vn 1. To dismantle, we must take out vn at a cost of f(1). We
must also remove all but one of v1;::: ;vn 1 at a cost of (n 2) f(12). Thus, the cost of
dismantling with this weighting is f(1) + (n 2) f( 12) = M2.
Let x 2 (0; 12]. Consider the weighting where we put x on v1 and 1 x on v2;::: ;vn.
If v1 is not knocked out, then all the other vertices must be, for strict dismantling, at a
cost of (n 1) f(1 x). If v1 is knocked out, then the dismantling is most economically
achieved by further knocking out each of v2;::: ;vn 2 (since 1 x 12, two adjacent
vertices with weight 1 x cannot be left, but since 1 x < 1, vn and vn 1 can be
left); the cost of this particular dismantling is f(x) + (n 3) f(1 x). Thus the cost of
dismantling with these weights is min[(n 1)f(1 x);f(x) + (n 3)f(1 x)].
Claim 1 If f(0) 2f(1), then for each x 2 [0; 12], f(x) + (n 3)f(1 x) f(1) + (n
2)f(12).
15
Proof of Claim 1 If f(0) 2f(1) and 0 x 12, then 12 1 x 1 and so
2f(1) f(0) f(x) f(12) f(1 x) f(1). From this long inequality, we get that
f(x)+(n 3)f(1 x) = f(x) f(1 x)+(n 2)f(1 x) 2f(1) f(1 x)+(n 2)f( 12)
2f(1) f(1) + (n 2)f(12) = f(1) + (n 2)f(12) as in the statement of the claim.
Suppose that 2f(1) f(0). By de nition, M3 = M2 SH(Kn e;f). The following
observations will be helpful later. Because f is non-increasing, 2f(1 x) f(x) for each
x 2 (0; 12], so (n 1)f(1 x) f(x)+(n 3)f(1 x), for each x 2 (0; 12]. Thus the cost of
dismantling with this weighting is always f(x)+(n 3)f(1 x) if 2f(1) f(0), and the
greatest of these costs is incurred when f(x)+(n 3)f(1 x) achieves its max on (0; 12],
if it does achieve a max there. If it doesn?t, then f(x) + (n 3)f(1 x), a continuous
function, achieves its max on [0; 12] at 0, where its value is f(0)+(n 3)f(1) (n 1)f(1).
In either case, the maximum value of f(x)+(n 3)f(1 x) occurs on [0; 12] and by Claim
1 above, f(x) + (n 3)f(1 x) f(1) + (n 2)f( 12) = M2.
If f(0) > 2f(1) then, since f(12) 2f(12), and f(x) 2f(1 x) is continuous,
there is some x 2 (0; 12] satisfying f(x) = 2f(1 x), and since f is non-increasing, the
values of f(x) and f(1 x) are the same for di erent values of x satisfying the equation
f(x) = 2f(1 x). For any such x, f(x)+(n 3)f(1 x) = (n 1)f(1 x) is the cost of
dismantling Kn e equipped with this particular weighting. Thus M3 SH(Kn e;f)
in the case f(0) > 2f(1). Thus M3 SH(Kn e;f) in any case. This completes the
proof that max(M1;M2;M3) SH(Kn e;f).
Now we shall show that SH(Kn e;f) max(M1;M2;M3) by showing that for
every g : V (G) ! [0;1], where G = Kn e, there is a strict g-dismantling set S of
16
vertices of Kn e such that Pv2S f(g(v)) max(M1;M2;M3). (Note that we may as
well suppose that all weights are 1.) So, suppose g is such a weighting function, and
let g(vi) = xi, 1 i n.
Claim 2 It su ces to consider only weighting functions g such that g(vn 1);g(vn)
g(vi);1 i n 2.
Proof of Claim 2 Suppose g(vn) = xn < x1 = g(v1). Let us de ne ^g by ^g(vi) = xi
for 2 i n 1, ^g(vn) = x1, and ^g(v1) = xn. We will show that m(g;G) m(^g;G).
Suppose that S is a cheapest strict ^g-dismantling set of vertices; then Pv2S f(^g(v)) =
m(^g;G).
If v1;vn 62 S, or, if v1;vn 2 S, then S is a strict g-dismantling set (in the case
v1;vn 62 S, note that v1 and vn are in the same component of G S; indeed, G S
is connected in this case) and m(g;G) Pv2S f(g(v)) = Pv2S f(^g(v)) = m(^g;G). If
vn 2 S, v1 62 S, then let ~S = (S n fvng) [ fv1g. Note that G S is connected, since
v1 62 S, so we have Pv2V (G ~S) f(g(v)) = Pv2V (G S) f(^g(v)) < 1. Thus, ~S is a strict
g-dismantling set, and we have m(g;G) Pv2~S f(g(v)) = Pv2S f(^g(v)) = m(^g;G). For
the last case, if v1 2 S, vn 62 S, then S is clearly a strict g-dismantling set, and we have
m(g;G) Pv2S f(g(v)) Pv2S f(^g(v)) = m(^g;G). This establishes the claim.
So, we may as well assume that x1 x2 xn 1 xn 1. If xn = 1,
then vn must be removed, for strict dismantling, and then the (n 1)-clique G vn
must be dismantled, which can be accomplished at a cost no greater than SH(Kn 1;f).
17
Thus, if xn = 1, m(g;G) f(1) + max
1 k n 1
(n k)f(1k) max[M1;M2]. So assume that
x1 xn < 1.
If Pni=1 xi < 1 take S = ;. Otherwise, there is some k 2 f2;::: ;ng such that
Pk 1
i=1 xi < 1
Pk
i=1 xi kxk (so, xk
1
k). Take S = fvk;::: ;vng which is a strict
g-dismantling set with cost Pni=k f(xi) (n k + 1)f( 1k) M1, unless k = 2. Let us
now assume that k = 2. If x1 12, then 12 xi < 1, 1 i n. Dismantle by knocking
out v1;::: ;vn 2 at a cost of Pn 2i=1 f(xi) (n 2)f(12) M2. Therefore, we may assume
that x1 < 12. Since k = 2 we have 1 x1 + x2, so, 1 x1 x2 xn. Take S1 =
fv2;::: ;vng, which is a strict g-dismantling set with cost Pni=2 f(xi) (n 1)f(1 x1)
and take S2 = fv1;::: ;vn 2g, which costs Pn 2i=1 f(xi) f(x1) + (n 3)f(1 x1). So,
m(g;G) min[(n 1)f(1 x1);f(x1) + (n 3)f(1 x1)] M3;
by Claim 1 above, and associated arguments. [To see the inequality in the case when
f(0) > 2f(1) observe that f(1 x) is a non-decreasing function of x, and (f(x) + (n
3)f(1 x)) (n 1)f(1 x) = f(x) 2f(1 x) is therefore a non-increasing function
of x. The value of the di erence, h(x) = f(x) 2f(1 x), is positive when x = 0, and
non-positive when x = 12, and is therefore equal to zero at some ~x 2 (0; 12], since f is
continuous. Because h(x) is non-increasing on [0; 12], for x1 < 12, min[(n 1)f(1 x1),
f(x1)+(n 3)f(1 x1)] = min[(n 1)f(1 x1), (n 1)f(1 x1)+h(x1)] (n 1)f(1 ~x) =
M3.] This completes the proof that SH(Kn e;f) max(M1;M2;M3).
Corollary (of the proof). For any non-increasing, non-negative, continuous cost function
f, and any n 3, one of the following is a critical (most costly) weighting of Kn e,
with respect to f:
18
1. a constant weighting 1=k, for some k 2 f1;3;::: ;ng;
2. a weight of 1 on one of the vertices of degree n 2, with 12 on all the remaining
vertices;
3. a weight of x on one vertex of degree n 1 and a weight of 1 x on the other
vertices, if f(0) > 2f(1), where x 2 (0; 12] satis es f(x) = 2f(1 x).
2.2 Examples of di erent cost functions for each Mi
In this section, we present di erent cost functions fi such that SH(Kn e;fi) = Mi
for i = 1;2;3.
Let f1(x) = 1x. This cost function gives us the following values for M1;M2 and M3;
n 4.
M1 =
(n + 1)2
4
, M2 = 2n 3, M3 = 32(n 1).
It can easily be seen that for all n 4, M1 > max (M2;M3) and so by Theorem 2.1 we
have that SH(Kn e;f1) = M1.
Now let f2(x) =
8
><
>:
3 if 0 x 12
4x + 5 if 12 < x 1
. From this cost function, for n 3, we
get the following values:
M1 = 3n 6, M2 = 3n 5, M3 = 32(n 1).
Once again it can easily be checked that for all n 3, M2 > max(M1;M3) and thus by
Theorem 2.1 we have that SH(Kn e;f2) = M2.
19
Finally, let f3(x) =
8
>>>
>><
>>>
>>:
x(n + 2)(n + 1) + n + 3 if 0 x < 1n+1
1 if 1n+1 x n+1n+2
(n + 2)(x 1) if n+1n+2 < x 1
This cost function yields the following values:
M1 = n 2, M2 = n 2, M3 = n 1 .
In this case, obtaining the values of the M?s is a bit di cult but it is quite clear that
M3 > max(M1;M2). By Theorem 2.1, SH(Kn e;f3) = M3:
2.3 A counterexample to the constant weights on orbits conjecture
The constant weights on orbits conjecture (CWOC) has been posed as follows:
For all continuous non-increasing cost functions f and all graphs G, there is
an optimal weighting of V (G) which is constant on each orbit of V (G) under
Aut(G), the group of graph automorphisms of G.
It takes little imagination to see that this conjecture, if true, would be quite useful
in computing the SH numbers of intersecting cliques. However, as stated, the CWOC
is not true and a counterexample lies among the cost functions f on Kn e. In fact,
perhaps any cost function f that yields SH(Kn e;f) = M2 is such a counterexample.
The one which we present and prove is such a counterexample is the cost function f2
which was rst presented in section 2.2 (and which we will present again later in this
section).
In section 2.2, we presented the values of M1;M2 and M3 obtained from using f2 as
our cost function. From these values, it can easily be veri ed that max[M1;M2;M3] =
20
M2 = 3n 5, for n 3. We will now show that with f2 as our cost function, any
weighting that is constant on each orbit of G = Kn e is not an optimal weighting (i.e.
SH(G;f2) > mf2(g;G).
Proposition 2.1 Let g be any weighting that is constant on each orbit of G = Kn e.
Then SH(G;f2) > mf2(g;G) where f2 is de ned as follows:
f2(x) =
8
><
>:
3 if 0 x 12
4x + 5 if 12 < x 1
Proof. Let, as before, the vertices of Kn e be v1;::: ;vn with e = vn;vn 1. Let
a;b 2 [0;1] and let g be the weighting such that for each 1 i n
g(vi) =
8
><
>:
b if 1 i n 2
a if n 2 < i n
a95 a95
a95 a95
a96 a96
a96 a96 a97 a97
a97 a97
a98
a98
a99 a99a100
a101 a101a102
a103 a103a104
a105 a105a106 a106
a107 a107a108 a108
a109 a109a110 a110
a111 a111 a111 a111 a111 a111
a111 a111 a111 a111 a111 a111
a111 a111 a111 a111 a111 a111
a111 a111 a111 a111 a111 a111
a111 a111 a111 a111 a111 a111
a111 a111 a111 a111 a111 a111
a112 a112 a112 a112 a112 a112
a112 a112 a112 a112 a112 a112
a112 a112 a112 a112 a112 a112
a112 a112 a112 a112 a112 a112
a112 a112 a112 a112 a112 a112
a112 a112 a112 a112 a112 a112
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a113 a113 a113 a113 a113 a113
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a114 a114 a114 a114 a114 a114
a
vn 1 vn
a
all with weight b
v1; : : : ; vn 2
Kn 2
Figure 2.1: Kn e with constant on orbits weighting g
If a = b, then we nd that SH0(Kn e;f2) = max
1 k n
p(k;Kn e)f2(1k) = max[n;3(n
2)] = 3n 6. Clearly, 3n 6 < 3n 5 = M2 and so any weighting that is constant on the
21
vertices of Kn e is not an optimal weighting. Otherwise, if a 6= b, then by Claim 2 in
the proof of Theorem 2.1 we may as well assume that a > b. This leaves us a few cases
to consider. In each of the following cases, we look at how we can choose values of a and
b so as to maximize the cheapest dismantling cost of G with respect to the weighting g
and cost function f2.
Case 1: b < a 12 In this case, f2(g(v)) = 3 for all v 2 V (Kn e). So we want to force
the removal of as many vertices as we can. Choosing values of a and b so that 2a+b 1
will force the removal of n 2 vertices which will be the best we can do (since a+b < 1).
This results in mf2(g;Kn e) = 3(n 2) = 3n 6 < 3n 5 = M2 = SH(G;f2).
Case 2: b 12 < a < 1 Since for all b 12, f(b) = f(12) we may as well choose b = 12.
For any 12 < a < 1, we can force the removal of no more than n 2 vertices and so
mf2(g;Kn e) = 3(n 2) = 3n 6 < 3n 5 = M2 = SH(G;f2).
Case 3: b 12 < a = 14 In this case, f2(b) = 3 and f2(a) = 1. The two vertices of
weight a must be removed for strict dismantling and so we wish to force the removal of
as many of the n 2 vertices of weight b. Choosing b = 12 forces the removal of (n 2) 1
of the vertices of weight b which is the best we can do. mf2(g;Kn e) = 3(n 3) + 2 =
3n 7 < 3n 5 = M2 = SH(G;f2).
Case 4: 12 < b < a < 1 For strict dismantling, all remaining components after vertex
removal must contain no more than one vertex. Of all cheapest dismantling costs, the
maximum is achieved when the Kn 2 is removed and so mf2(g;Kn e) = f2(b)(n 2) <
3(n 2) = 3n 6 < 3n 5 = M2 = SH(G;f2).
Case 5: 12 < b < a = 1 For strict dismantling, vn 1 and vn must be removed at a cost
of 2f2(a) = 2. Since b > 12, (n 2) 1 = n 3 vertices of the Kn 2 must be removed at
22
a cost of f2(b)(n 3) and so mf2(g;Kn e) = f2(b)(n 3)+2 < 3(n 3)+2 = 3n 7 <
3n 5 = M2 = SH(G;f2).
Chapter 3
Some General Results
with Applications to Intersecting Cliques
In what follows, G will be an arbitrary nite simple graph with vertex set V (G), of
order n(G) = jV (G)j. For u 2 V (G), deg(u) will denote the degree of u in G and NG(u)
will denote the set of vertices adjacent to u in G.
3.1 A useful proposition
The following is a generalization of Claim 2 in the proof of Theorem 2.1.
Proposition 3.1 Suppose that T V (G) and for each u 2 T deg(u) = n(G) 1. For
any continuous f, there is an optimal weighting g of G satisfying g(u) g(v) for each
u 2 T and each v =2 T.
Proof. Let g be an optimal weighting of G, with respect to f (i.e., m(g;G) = SH(G;f)).
Now suppose that for some v =2 T;u 2 T;g(v) < g(u). De ne ^g by ^g(u) = g(v),
^g(v) = g(u), and ^g = g on V (G)nfu;vg. We shall show that ^g is an optimal weighting
of G with respect to f. This will prove the proposition, since, even if ^g does not satisfy
the requirement of the conclusion, we can go on switching values until we arrive at a
weighting that does satisfy that requirement, and this nal weighting will be optimal.
Let S V (G) be a strict ^g-dismantling set such that m(^g;G) =
P
w2S f(^g(w)). If neither u nor v, or if both u and v, belong to S, then S is a strict
g-dismantling set, whence SH(G;f) m(^g;G) = Pw2S f(^g(w)) = Pw2S f(g(w))
23
24
m(g;G) = SH(G;f), and it follows that ^g is an optimal weighting of G, with respect to
f. This leaves two cases to consider.
v 2 S, u =2 S : in this case, because u 2 T is not in S, G S is connected, and
P
w2V (G)nS ^g(w) < 1. Let ~S = (Snfvg)[fug. Then
P
w2V (G)n~S g(w) =
P
w2V (G)nS ^g(w) <
1 so ~S is a strict g-dismantling set, and so m(g;G)
P
w2~S f(g(w)) =
P
w2S f(^g(w)) = m(^g;G). The conclusion that ^g is an optimal weight-
ing follows as before.
v =2 S, u 2 S : In this case, S is a strict g-dismantling set and m(g;G) Pw2S f(g(w))
P
w2S f(^g(w)) = m(^g;G) because ^g(u) < g(u) and f is non-increasing. The conclusion
that ^g is optimal follows as before.
For 0 < s < l;r, denote by G(l;r;s) the graph consisting of a Kl and a Kr inter-
secting in a Ks, as indicated in Figure 3.1 below.
Kl Ks Kr
Figure 3.1: G(l;r;s)
Corollary 3.1 For any continuous f, there is an optimal weighting g of G(l;r;s) with
g(u) g(v) for every u in the Ks and every v not in the Ks.
Proof. The proof of this corollary follows immediately from Proposition 1 by taking
T = V (Ks).
25
3.2 Limits of Optimal Weightings
Proposition 3.2 If f is continuous and gn is an optimal weighting of G for each n =
1;2;3;::: and gn(v) ! g(v) as n ! 1 for each v 2 V (G), then g is an optimal weighting
of G.
Proof. Since each weighting gn is an optimal weighting of G, mf(gn;G) = SH(G;f)
for each n. Now, let S be a strict g-dismantling set of vertices of least cost with
P
v2S f(g(v)) = mf(g;G) SH(G;f). We now show that S is a strict gn-dismantling
set for all n su ciently large by showing that for such n and for each component H of
G S, Pv2V (H) gn(v) < 1.
Since S is a strict g-dismantling set, then for each component H of G S we
have limn!1 Pv2V (H) gn(v) = Pv2V (H) g(v) < 1. Thus, there exists some integer NH
such that n NH implies that Pv2V (H) gn(v) < 1. There are only nitely many such
H; take N = maxH a component of G-S NH ; then n N implies that for each such H ,
P
v2V (H) gn(v) < 1.
Now for all n su ciently large we have the following:
SH(G;f) = mf(gn;G) Pv2S f(gn(v)) ! Pv2S f(g(v)) = mf(g;G).
This gives us that mf(g;G) SH(G;f). Since mf(g;G) SH(G;f), g is an optimal
weighting of G.
De nition f : I ! R is concave on an interval I if and only if for all x;y 2 I and t 2 [0;1],
f(tx + (1 t)y) tf(x) + (1 t)f(y).
26
Proposition 3.3 Suppose f is continuous and concave on [0;1] and S V (G) satis es:
for each u;v 2 S;NG(u)nfvg = NG(v)nfug. Suppose either that f(1) = 0 or that S
induces a clique in G. Then for any optimal weighting g of G, there is another optimal
weighting ~g of G which is constant on S, agrees with g on V (G)nS, and minv2S g(v)
~gjS maxv2S g(v). Further, if S1;S2;::: ;Sk are disjoint sets of vertices of G each
satisfying the suppositions above, then there is an optimal weighting ^g of G which is
constant on each Si;i = 1;2;::: ;k, agrees with g at vertices not in any Si, and, for each
i, minv2Si g(v) ^gjSi maxv2Si g(v).
Proof. Suppose we have an optimal weighting g of G with respect to f, so mf(g;G) =
SH(G;f). Let S V (G) be such that for each u;v 2 S with u 6= v, NG(u) n fvg =
NG(v)nfug. We further suppose that either f(1) = 0 or S induces a clique in G. If g is
constant on S we can take ~g = g, so assume that g is not constant on S. Let u0, u1 2 S
such that g(u0) = min
v2S
g(v) < g(u1) = max
v2S
g(v):
Now let us de ne a weighting ^g by ^g = g except at u0 and u1 where ^g(u0) =
^g(u1) = g(u0)+g(u1)2 . We will show that mf(^g;G) mf(g;G), which implies mf(^g;G) =
SH(G;f).
Let T V (G) be a strict ^g-dismantling set of least cost, so mf(^g;G) =
P
v2T f(^g(v)). We have four cases to consider:
Case 1: u0 =2 T, u1 2 T In this case, for any connected component H of G T,
P
u2V (H) g(u)
P
u2V (H) ^g(u) < 1 since g(u0) < ^g(u0) and u0 =2 T. Thus T is a strict
g-dismantling set, so mf(g;G) Pu2T f(g(u)) Pu2T f(^g(u)) = mf(^g;G) because f
is non-increasing.
27
Case 2: u0 2 T, u1 =2 T If this occurs, we can nd another set T1 = (T n fu0g) [ fu1g
with a dismantling cost equal to Pv2T f(^g(v)), because ^g(u0) = ^g(u1). T1 is a strict
^g-dismantling set of vertices because T is, and u0 and u1 have the same neighbors other
than themselves. Since, by assumption, T is a cheapest strict ^g-dismantling set, T1 must
be one as well. Further, T1 satis es the requirement de ning Case 1, so we are done in
this case.
Case 3: u0 =2 T, u1 =2 T If u0 and u1 are adjacent, then u0 and u1 will be in the same
component of G T. Then for every connected component H of G T, Pu2V (H) g(u) =
P
u2V (H) ^g(u) < 1. So T is a g-dismantling set, whence mf(g;G)
P
v2T f(g(v)) =
P
v2T f(^g(v)) = mf(^g;G). Now if u0 and u1 are not adjacent, then S does not induce
a clique in G, so f(1) = 0. Now u0 and u1 may possibly not be in the same component
of G T. If they are in the same component, then T is a strict g-dismantling set and
we are done. If they are not, then u0 and u1 are isolated vertices in G T because they
have the same neighbor sets in G. We know that Pu2V (H) g(u) Pu2V (H) ^g(u) < 1 for
every connected component H of G T except the H consisting of the vertex u1. Now if
g(u1) < 1 then T is a g-dismantling set and we are done. If g(u1) = 1 then f(g(u1)) = 0
and so T [ fu1g is a strict g-dismantling set with the same cost as T. We have that
mf(g;G) Pv2T[fu1g f(g(v)) = Pv2T f(g(v)) = Pv2T f(^g(v)) = mf(^g;G).
Case 4: u0 2 T, u1 2 T In this case, it is clear that for every connected component H of
G T, Pu2V (H) g(u) = Pu2V (H) ^g(u) < 1 and so T is a strict g-dismantling set. Now,
mf(^g;G) = Pv2T f(^g(v)) = Pv2T f(g(v)) [f(g(u0)) + f(g(u1))] + 2[f(g(u0)+g(u1)2 )]
mf(g;G) f(g(u0)) f(g(u1))+2[f(12g(u0)+ 12g(u1))] mf(g;G) since f is concave.
This completes the proof that ^g is optimal.
28
Now for any weighting h of G let d(h) = maxu2S h(u) minu2S h(u). We will
show that for every optimal weighting h of G with d(h) > 0 there is another optimal
weighting ~h satisfying the following: d(~h) < d(h), ~h(v) = h(v) for all v 2 V (G)nS, and
minv2S h(v) ~hjS maxv2S h(v).
Let h be any optimal weighting of G with d(h) > 0 and let h1 = ^h, obtained
as above. By the de nition of ^h, h(v) = h1(v) for all v 2 V (G S), and clearly
minv2S h(v) minv2S h1(v) maxv2S h1(v) maxv2S h(v). Therefore d(h1) d(h).
If d(h1) < d(h), take ~h = h1. Otherwise, we have d(h1) = d(h) > 0, which implies
that maxv2S h1(v) = maxv2S h(v) and minv2S h1(v) = minv2S h(v). Note that the set of
vertices in S where h1 achieves its maximum is the set of vertices in S where h achieves
its maximum, minus one vertex, and the same holds for the sets of points where h and
h1 achieve their minimum on S.
Let h2 = ^h1. If d(h2) < d(h), take ~h = h2. Otherwise, continue, letting h3 = ^h2, and
so on. In going from hi 1 to hi, one vertex of S at which hi 1 is maximal has its weight
decreased, and one vertex at which hi 1 is minimal has its weight increased, and these
are vertices at which h is maximal, respectively minimal. Since there are only a nite
number of such vertices, we must have d(hi) < d(h) eventually. It is straightforward to
see that ~h = hi has the desired properties.
Suppose that g is an optimal weighting of G and suppose that W = fh : V (G) !
[0;1];h is an optimal weighting of G, h g on V (G)nS, and minv2S g(v) hjS
maxv2S g(v)g contains no weightings which are constant on S. Let d = inf[d(h);h 2 W].
By the meaning of inf, for each positive integer k, there is a weighting hk 2 W with
d d(hk) < d + 1k. Then (hk) is a sequence of optimal weightings. Since the hk are
29
bounded functions on a nite set, V (G), the sequence (hk) has a convergent subsequence;
to avoid proliferation of subscripts, let us suppose that (hk) itself is convergent, i.e., for
each v 2 V (G), (hk(v)) converges to some value h(v).
By Proposition 3.2, the weighting h is optimal, and it clearly satis es the other
requirements for membership in W. We claim that d(h) = d. It is certainly clear by
the de nition of d that d d(h). Let u0;u1 2 S be such that h(u1) = maxu2S h(u)
and h(u0) = minu2S h(u). Then d(h) = h(u1) h(u0) = limk!1(hk(u1) hk(u0))
limk!1 d(hk) since for each hk, d(hk) is the maximum distance between the values of
hk at two vertices in S. Thus, d(h) d. Since d d(h) and d(h) d then d(h) = d
as claimed. If d = 0 then h is an optimal weighting with d(h) = 0, so such a weighting
satisfying all conditions of the proposition must exist after all, contrary to supposition.
If d(h) > 0 then by previous remarks there is another optimal weighting ~h 2 W with
d(~h) < d(h) = d. But this contradicts the de nition of d, by which d is a lower bound of
a collection of numbers of which d(~h) is one. So there must be an optimal weighting of
G which is constant on S satisfying all the conditions of the proposition after all.
Now suppose that S1;::: ;Sk are pairwise disjoint sets of vertices, each satisfying the
conditions of the proposition. We proceed by induction on k. We may as well suppose
that k > 1. By the induction hypothesis, there is an optimal weighting ^gk 1 of G, with
respect to f, which is constant on each of S1;::: ;Sk 1, agrees with g o
k 1[
i=1
Si, and
whose constant value on Si is between the max and min values of g on Si, for each
i = 1;::: ;k 1. If we let Sk play the role of S and ^gk 1 replace g in the argument above
we get an optimal weighting ^g that satis es the conclusion of the proposition.
30
Corollary 3.2 If f is continuous and concave on [0;1], there is an optimal weighting of
G(l;r;s) satisfying the conclusion of Corollary 3.1 which is constant on each of KlnKs
and KrnKs, and Ks.
Proof. Let g be an optimal weighting of G(l;r;s) satisfying the conclusion of Proposition
3.1 and which is possibly not constant on Kl Ks;Kr Ks and/or Ks. Now let S1 =
V (Kl Ks);S2 = V (Kr Ks) and S3 = V (Ks). S1;S2 and S3 are disjoint sets of vertices
which satisfy the conditions of Proposition 3.3. Applying Proposition 3.3 to G(l;r;s)
with the weighting g of Corollary 1 will then yield a new optimal weighting ^g which will
satisfy the conclusion of the corollary.
3.3 An application of Proposition 3.3 and other useful results
The goal of this section is to present an application of some of the results presented
here in Chapter 3. We do this with special emphasis on an application of Proposition 3.3
in order to illustrate how it can be used to simplify and reduce the number of calculations
that are often required in computing the Shields-Harary numbers. It should be noted that
Proposition 3.3 arose out of an attempt to compute the SH numbers of two intersecting
cliques for general continuous cost functions with non-constant weightings. The main
usefulness of Proposition 3.3 lies in the fact that for any graph G containing a set or
disjoint sets of vertices satisfying the requirements of the proposition, if the cost function
is concave we can restrict the search for optimal weightings to weightings constant on that
set or those sets. This reduces the number of unknowns in the calculation of SH(G;f).
We illustrate this in proving the following corollary.
31
Corollary 3.3 Let G =
a115a116 a117 a117a118
a119 a119a120a121a122 .
Then SH(G;1 x) = 43
Proof. Let S1 consist of the two vertices of G of degree 2 and let S2 consist of the two
vertices of G of degree 3. Since 1 x is concave on [0;1] and S1 and S2 are disjoint
sets of vertices satisfying the requirements of Proposition 3.3, then as a result of the
proposition, the computation of SH(G;1 x) requires only considering those weightings
which are constant on each of S1 and S2.
Now suppose that our weighting g puts weights a and b on the vertices of S1 and S2
respectively. Since G = K4 e, then by Corollary 3.1, we know that there is an optimal
weighting with f(x) = 1 x such that b a. So we may as well assume that a b.
Suppose that S is a cheapest g-dismantling set of vertices of G. We have several
cases to consider:
Case 1: a;b 12 We may as well let a = b = 12 in this case. This gives us that S = S2
with a g-dismantling cost of 2f(12) = 2(1 12) = 1.
Case 2: a 12;b < 12 We can drive the cheapest dismantling cost as high as possible by
choosing a = 12. This yields S = S1 with a g-dismantling cost of 2f(12) = 1.
Case 3: a;b < 12 If 2b + a < 1 then S ( S1 with a g-dismantling cost of f(a) = 1 a <
1. In this event, Cases 1 and 2 yield a higher cheapest dismantling cost. Otherwise,
2b + a 1 =) a 1 2b. Again, we can drive the cheapest dismantling cost as high
32
as possible by choosing a = 1 2b. This yields S = S1 with a g-dismantling cost of
2f(a) = 2(1 a) = 2(1 1+2b) = 4b. However, a b =) 1 2b b =) b 13. So to
make 4b as high as possible, we choose b = 13. Thus, if 2b +a 1, S has a g-dismantling
cost of 43.
As a result, SH(G;1 x) = max[1;1; 43] = 43.
Note: Since G = K4 e, we could just as easily have used Theorem 2.1 to compute
SH(G;1 x). If so, the results would be that SH(G;1 x) = max[M1;M2;M3] =
max[max[0; 43; 34]];1;1] = 43 as computed above.
Clearly, Theorem 2.1 provides a shorter route in this particular case. Since Kn e
is just a special case of two intersecting cliques (namely two K3?s intersecting in a K2),
this serves as no big surprise. However, in the more general setting, where Theorem
2.1 will not always apply, we can see how useful Proposition 3.3 can be in its use in
the calculation above. In this particular case we only had to consider two unknown
quantities as opposed to four.
We now consider some other applications of these propositions. If G = G(3;3;1)
and f(x) = 1 x, then SH(G;f) = 32. Corollary 3.2 tells us that there will be an optimal
weighting of G as illustrated in Figure 3.2 where either (1)a b x or (2)b a x.
Clearly, we may look for a weighting satisfying (1) without loss of generality.
a123a124
a125a126
a127a128
a129a130
a131a132
a133 a133 a133
a133 a133 a133
a133 a133 a133
a134 a134 a134
a134 a134 a134
a134 a134 a134a135 a135 a135
a135 a135 a135
a135 a135 a135
a136 a136 a136
a136 a136 a136
a136 a136 a136
a137 a137 a137
a137 a137 a137
a137 a137 a137
a138 a138 a138
a138 a138 a138
a138 a138 a138
a139 a139 a139
a139 a139 a139
a139 a139 a139
a140 a140 a140
a140 a140 a140
a140 a140 a140a
a
b
b
x
.
Figure 3.2: G(3;3;1)
33
The simpli cation provided by Corollary 3.2 in the problem of determining
SH(G(l;r;s);f) for any concave cost function f is mainly to reduce the number of
variables involved from l + r s(= 5 in this case) to 3. The additional restriction
that f(1) = 0 allows us the assumption that a;b;x < 1. Even with these simpli ca-
tions, and even with a particular cost function f, the analysis necessary to determine
SH(G(l;r;s);f) and (what may be more important) an optimal weighting of the ver-
tices of G, will be rather tedious and involved and we leave an illustration of the proof
of SH(G(3;3;1);1 x) = 32 to the work done in [4].
We can explore this situation even further by considering the graph G(3;3;1) with
the cost function f(x) = 2 x. In this case, it turns out that SH(G(3;3;1);2 x) = 5.
Now, the analysis is complicated by the possibility of using 1 as a weight. Any vertex
with weight 1 must be removed in strict dismantling and with f(x) = 2 x it turns out
to be optimal to use 1 as a weight. In fact, two optimal weightings with f(x) = 2 x
are given by a = b = x = 1 and a = 1;b = x = 12.
In the case of a complete r-partite graph Kn1;:::;nr;r 2, and a concave function
satisfying f(1) = 0, the application of Proposition 3.3 allows us to look for optimal
weightings which are constant on each part of size ni 2, and constant on the clique
formed by the parts with only one vertex. Thus, the number of variables is reduced from
n =
rX
i=1
ni either to r s + 1 or to r, if s = fi;ni = 1g = 0. Thus, for the complete
bipartite graphs Km;n, except for K1;1 = K2 and such a cost function, there are only
two variables to worry about, the constant weights on each part.
Chapter 4
The Shields-Harary Numbers of Km;n for Some Cost Functions
4.1 Some generalities
Throughout, let Km;n have parts M and N with jMj = m n = jNj, and let f be
some continuous non-increasing cost function.
Lemma 4.1 Suppose a;b 2 (0;1) and g is the weighting of the vertices of G = Km;n
constantly equal to a on M and to b on N. Then there is a strict g-dismantling set S of
least cost (with respect to f) satisfying one of the following:
(i) S = M;
(ii) S = N ;
(iii) S ( M ;
(iv) S ( N.
Further, if a > b then possibility (iv) can be excluded, and if a b then possibility (iii)
can be excluded.
Proof. Since a;b < 1, choosing either S = M or S = N strictly g-dismantles G.
Also, any set of vertices of G whose removal disconnects G will contain either M or N.
Therefore, one of M or N is a strict g-dismantling set of least cost among those (if any)
whose removal disconnects G.
Now we consider the cases in which there is a strict g-dismantling set ^S of minimum
cost such that G ^S is connected, and ^S is neither M nor N (G N is connected if
m = 1, and G M is connected if m = n = 1).
34
35
Case 1: a > b If ^S ( M, we are done, so suppose that ^S = ^M [ ^N, ^M ( M, ; 6= ^N ( N.
If j ^Nj jM ^Mj, then we can nd a no more expensive g-dismantling set S of vertices
by de ning S = M. Otherwise, we can still nd a cheaper g-dismantling set S of vertices
by de ning S = ( ^S ^N) [ ^M2 where ^M2 ( M ^M and j ^M2j = j ^Nj. Since, in either
case, S consists only of vertices with weight a and jSj is never more than j ^Sj, we can
certainly do no better.
Thus, if a > b, then there is a strict g-dismantling set S of least cost such that either
S = M or S ( M.
Case 2: a b If ^S ( N we are done, so, as in Case 1, suppose that ^S = ^M [ ^N, ^N ( N,
; 6= ^M ( M. If j ^Mj jN ^Nj, then we can nd a no more expensive g-dismantling
set S of vertices by de ning S = N. Otherwise, we can still nd a no more expensive
g-dismantling set S by de ning S = ( ^S ^M) [ ^N2 where ^N2 ( N ^N and j ^N2j = j ^Mj.
Since, in either case, S consists only of vertices of weight b and jSj is never more than
j^Sj, we can certainly do no better.
So, if a b, then there is a strict g-dismantling set S of least cost such that either
S = N or S ( N.
Lemma 4.2 Among weightings constant on M and on N, there is one of greatest strict
dismantling cost whose value on M is less than or equal to its value on N.
Proof. Throughout, suppose a < b 1 and let f be some continuous, non-increasing
cost function and G = Km;n . Let ~g be a weighting of the vertices of G constantly equal
to a on M and b on N. Now let g be a weighting of the vertices of G constantly equal
to b on M and a on N. We will show mf(~g;G) mf(g;G), which implies the result.
36
Let S be a cheapest strict g-dismantling set of vertices of G and let ~S be a cheapest
strict ~g dismantling set of vertices of G . If b = 1, then because of the requirement of
strict dismantling, S = M and ~S = N; since n m, our result follows in this case.
Otherwise, b < 1 and so by Lemma 4.1, we only need consider the cases where S = M,
S = N or S ( M and for ~S, ~S = M, ~S = N or ~S ( N.
Case 1: S = M If S = M, then S has g-dismantling cost of mf(b), so mf(g;G) = mf(b).
If G ~S is disconnected, then either ~S = M and so mf(~g;G) = mf(a) mf(b) =
mf(g;G) or ~S = N in which case mf(~g;G) = nf(b) mf(b) = mf(g;G). Otherwise,
G ~S is connected and so we may assume that ~S ( N. So let j~Sj = k. If k m, then
mf(~g;G) = kf(b) mf(b) = mf(g;G). Otherwise, k < m.
Since S is a strict g-dismantling set, then na + b 1. Now, since ~S is a cheapest ~g
dismantling set, then it must be the case that (n k)b+ma < 1. However, (n k)b+ma
na + b 1 whenever b(n (k + 1)) a(n m) which is true when k < m since
n (k + 1) n m whenever k < m. This implies that k m and so we are done with
this case.
Case 2: S = N If S = N, then S has g-dismantling cost of nf(a). Clearly mf(b)
nf(a), and M is a dismantling set for g, so this case can be dismissed.
Case 3: S ( M If S ( M, then mf(g;G) = lf(b) where l = jSj. Now suppose that
~S = N, in which case mf(~g;G) = nf(b) lf(b) = mf(g;G) or if ~S = M, then
mf(~g;G) = mf(a) lf(b) = mf(g;G). So if G ~S is disconnected, then mf(~g;G)
mf(g;G). Now, if G ~S is connected, then we may assume that ~S ( N and so let
j~Sj = k. If k l, then mf(~g;G) = kf(b) lf(b) = mf(g;G). Since ~S is a strict
~g-dismantling set, (n k)b + ma < 1. Now, since S is a cheapest strict g-dismantling
37
set, we know that (m l +1)(b)+na 1. Therefore, (m l +1)b+na > (n k)b+ma,
which implies that 0 (n m)(a b) > (l (k + 1))b. Thus, l k.
Lemma 4.3 Among all weightings of G = Km;m constantly equal to a on one partition
of G and constantly equal to b on the other partition of G, there is one of greatest strict
dismantling cost such that a = b.
Proof. Let g be a weighting of G = Km;m such that weight a is assigned to the vertices
of one partition, which we shall call Ma and weight b is assigned to the vertices of the
other partition of G which we shall call Mb. Without loss of generality, we may as well
assume that a > b. Now let ~g be the weighting of G such that weight a is assigned to all
of the vertices of G. We shall show that mf(~g;G) mf(g;G).
Let ~S be a cheapest strict ~g-dismantling set of vertices. By Lemma 4.1 and since
a > b either ~S = Ma or ~S ( Ma (likewise for the cheapest g-dismantling set of vertices).
These are the two cases that we must consider.
If ~S = Ma, then it must be the case that m(a)+a 1 and mf (~g;G) = mf(a). Since
~S disconnects G, then ~S is also a g-dismantling set of vertices, though not necessarily the
cheapest g-dismantling set of vertices. If mb+a 1 then since ma+a mb+a, ~S is also
the cheapest g-dismantling set of vertices and so mf(g;G) = mf(~g;G). Otherwise, the
cheapest g-dismantling set of vertices is a proper subset of ~S and so mf(g;G) < mf(~g;G).
If ~S ( Ma then ma+a < 1 and there is some 0 < k < m such that (m k)a+ma < 1
and (m k + 1)a + ma 1. This gives us that mf(~g;G) = kf(a). Since a b,
(m k)a + mb (m k)a + ma < 1 which implies that the cardinality of the cheapest
g-dismantling set is no greater than the cardinality of ~S. As the vertices of both of these
sets are coming from Ma (because a b), mf(g;G) mf(~g;G).
38
Corollary 4.1 If f is non-increasing, continuous and concave on [0,1] and f(1) = 0,
then SH(Km;m;f) = SH0(Km;m;f).
Proof. Since M and N satisfy the requirements on the Si in Proposition 3.3, it follows
from that proposition that there is an optimal weighting of Km;n which is constant on
each of M and N. By lemma 4.3, therefore, there is an optimal weighting of Km;n which
is constant, which proves the claim.
Corollary 4.2 SH(G = Km;m;1 x) = m
2
m + 1 and the constant weighting
1
m+1 is
optimal.
Proof. Since f(x) = 1 x is non-increasing, continuous and concave on [0;1], and
f(1) = 0, then we can apply corollary 4.1 and so only need worry with weightings which
are constant on G.
By the above paragraph, SH(G;1 x) = SH0(G;1 x) = max
1 k n
p(k;G)f
1
k
(a
result stated in Chapter 1). Now p(k;G) is the minimum cardinality of a set of vertices of
V (G) such that each component of G S has k 1 or fewer vertices). In fact, p(k;G)f( 1k)
is the dismantling cost when the vertices bear the constant weight 1k. For G = Km;m,
we get the following, with n = 2m:
39
p(1;G) = 2m
p(2;G) = m
p(3;G) = m
...
p(m 1;G) = m
p(m;G) = m
p(m + 1;G) = m
p(m + 2;G) = m 1
p(m + 3;G) = m 2
...
p(m + k;G) = m k + 1
...
p(2m 1;G) = 2
p(2m;G) = 1
So max
1 k n
p(k;G)f(1k) = max
1 k m
p(k;G)f
1
k
;p(m + k;G)f
1
m + k
= max
1 k m
m
1 1k
;(m k + 1)
1 1m + k
.
Now the value m(1 1k) attains its maximum value when k = 2 to get a value of m2 .
The value (m k+1)(1 1m+k) attains its maximum value at k = 1 (as it is a decreasing
function of positive k) and that value is (m)(1 1m+1) = m2m+1 > m2 . As a result,
SH(Km;m;1 x) = max
1 k n
p(k;G)f(1k) = m
2
m + 1, and the constant weighting
1
m+1 is
optimal.
40
Lemma 4.4 Suppose that 1 m n. There is an integer k 2 f1;::: ;n 1g satisfying
k(n k)
n k+1 m if and only if n m + 2
pm.
Proof. Solving x(n x)n x+1 m for x, assuming x 2 [1;n 1], so that n x+1 2 > 0, we get
that x2 (n+m)x+m(n+1) 0 which has a real solution x, n+m
p
(n+m)2 4m(n+1)
2
x n+m+
p
(n+m)2 4m(n+1)
2 , if and only if (n + m)
2 4m(n + 1) = (n m)2 4m 0,
i.e. if and only if n m 2pm (recollect that n m 0), or n m + 2pm.
Now suppose that n m + 2pm. We want to know if
n+m
p
(n m)2 4m
2 ;
n+m+
p
(n m)2 4m
2
T
f1;::: ;n 1g 6= ;.
First of all, it can easily be veri ed that 1 n+m
p
(n m)2 4m
2 n 1, so [c;d] =
n+m
p
(n m)2 4m
2 ;
n+m+
p
(n m)2 4m
2
will contain an integer among 1;::: ;n 1 unless
d < n 1 and d c < 1. If d = c, i.e. (n m)2 4m = 0, meaning n = m + 2pm (note
m is a perfect square), then n m mod 2 so c = d = n+m2 is an integer, and is clearly
in the right range (i.e., is among 1;::: ;n 1).
If d > c then (n m)2 4m > 0 =) (n m)2 4m 1 =) p(n m)2 4m =
d c 1, and we are done.
Lemma 4.5 SH(Kn;1 x) = max
k=1;:::;n 1
k(n k)
n k + 1.
Proof. From [2], we know that SH(Kn;1 x) = max
k=1;:::;n
(n k+1) f 1k (where f(x) = 1
x) = max
k=2;:::;n
(n k+1)f
1
k
= max
k=1;:::;n 1
kf
1
n k + 1
= max
k=1;:::;n 1
k
1 1n k + 1
= max
k=1;:::;n 1
k(n k)
n k + 1.
Remark: Applying a little calculus to g(x) = x(n x)n x+1 shows that it achieves its max
on [1;n 1], n 3, at n + 1 pn + 1 (and that max is (pn + 1 1)2). It follows
from this and the analysis of g that g achieves its max on the integers 1;::: ;n 1 at
41
either n + 1 pn + 1, if n + 1 is a perfect square, or at one of the 2 integers closest to
n + 1 pn + 1, namely, n + 1 dpn + 1e or n + 1 bpn + 1c.
Proposition 4.1
SH(Km;n; 1 x) =
8
><
>:
m if n m + 2pm
max[ 1n+1b(n+m)24 c; SH(Kn; 1 x)] < m if m n < m + 2pm
Proof. For any weighting of Km;n with weights from [0;1], take M together with all
vertices of N which are weighted 1, for a dismantling cost m. Thus SH(Km;n;1 x)
m.
Suppose that m n < m + 2pm. Let k = bn+m2 c. Weight each vertex of N with
b = k+1 mn+1 , and each vertex of M with a = 1 k(n+m k)m(n+1) . Note that a is positive because
k(n + m k) (n+m)24 , so k(n+m k)m(n+1) (n+m)24m(n+1) < 1 because m n < m + 2pm implies
(n m)2 < 4m, so (n + m)2 = (n m)2 + 4mn < 4m(n + 1).
It is straightforward to verify that m(1 a) = k(1 b) and that ma+(n k+1)b = 1.
Therefore Km;n with this weighting can be dismantled by removing M, or k vertices of
N, at the identical (minimum) cost of k(1 b) = k(n+m k)n+1 = 1n+1b(m+n)24 c. Thus
SH(Km;n;1 x) 1n+1b(n+m)24 c if m n < m + 2pm.
Now suppose that n m + 2pm. By Lemma 4.4, for some k 2 f1;::: ;n 1g,
k(n k)
n k+1 m. Weight M with 0 and each vertex of N with
1
n k+1. Then the only
dismantling sets competing with M are the k-subsets of N; but each of these costs
k(1 1n k+1) = k(n k)n k+1 m. Thus M is the cheapest dismantling set, at a cost of m, so
we have SH(Km;n;1 x) m; thus SH(Km;n;1 x) = m if n m + 2pm.
Now suppose that m n < m + 2pm. We want to show that SH(Km;n;1 x) =
max[ 1n+1b(n+m)24 c;SH(Kn;1 x)] and that this value is < m.
42
By Proposition 3.3 and Lemma 4.2, there is an optimal weighting of the vertices of
Km;n constant on each of M and N, with the weight on M no greater than that on N.
Let a denote the weight on M and b the weight on N; keep in mind that a b.
Suppose that a = 0. We must have that b < 1 (if b = 1, we can dismantle by
removing N, at no cost) and nb 1 (otherwise, if nb < 1, the empty set is dismantling,
again at no cost). Therefore, for some k 2 f1;::: ;n 1g, (n k)b < 1 (n k + 1)b.
By Lemma 4.1, the cheapest dismantling set is either M (at a cost of m) or S N,
jSj = k. Since reducing b down to 1n k+1 will not change that fact, but will increase
the cost of S, by the fact that our weighting is optimal we may as well suppose that
b = 1n k+1. Then the cost of S is k(1 1n k+1) = k(n k)n k+1 < m, by Lemma 4.4 (since
m n < m+2pm), so S is the cheapest (or, cheaper) dismantling set, and SH(Km;n;1
x) = k(n k)n k+1. Since we may as well take k 2 f1;::: ;n 1g so that k(n k)n k+1 is maximized,
we conclude that SH(Km;n;1 x) = SH(Kn;1 x), by Lemma 4.5, if a = 0 in the
optimal weighting.
Also, weighting with a = 0 and b = 1n k+1, where k 2 f1;::: ;n 1g maximizes
k(n k)
n k+1, shows that SH(Km;n;1 x) SH(Kn;1 x), if m n < m+2
pm. Therefore,
SH(Km;n;1 x) max[ 1n+1b(n+m)24 c;SH(Kn;1 x)] if m n < m + 2pm, and it
remains to demonstrate the reverse inequality. We have disposed of the case when there
is an optimal weighting with a = 0 on M.
Now suppose that a > 0 (and m n < m + 2pm). Again, from Lemma 4.1, we
have that our cheapest dismantling set S will be one of three, either S = M, S = N or
S ( N. We now consider each of these three cases.
43
Case 1: S = M We may as well assume that SH(Km;n;1 x) = m(1 a) > 1n+1b(n+m)24 c.
Noting that 1n+1b(n+m)24 c mnn+1, we have that m(1 a) > mnn+1 and thus that a < 1n+1.
Case 1A: ma + b 1 If ma+b 1, then b 1 ma > 1 mn+1 = n m+1n+1 and
(since S is a cheapest g-dismantling set) m(1 a) n(1 b) =) m + nb
n + ma < n + mn+1 =) b < n mn + mn(n+1). So if m(1 a) > mnn+1, b satis es
n m+1
n+1 < b <
n m
n +
m
n(n+1). However,
n m+1
n+1 <
n m
n +
m
n(n+1) =) 0 < 0.
This contradiction disposes of this case.
Case 1B: ma + (n k)b < 1 ma + (n k + 1)b for some k 2 f1;::: ;n 1g.
Since S is a cheapest g-dismantling set, we also have that m(1 a)
k(1 b) =) b 1 m(1 a)k and from the original inequality here in
the case 1B, we have that 1 man k+1 b < 1 man k .
Claim If a > 0 then it must be the case that ma + (n k + 1)b = 1 and
m(1 a) = k(1 b).
Proof of Claim If both ma + (n k + 1)b > 1 and m(1 a) < k(1 b),
reduce a slightly without changing b, so that the new value ~a, still positive,
satis es m~a + (n k + 1)b 1 and m(1 ~a) k(1 b). Then S = M is
still a cheapest dismantling set with respect to the new weighting, but then
~a < a =) SH(Km;n;1 x) = m(1 a) < m(1 ~a) SH(Km;n;1 x), a
contradiction. Therefore, it is not possible that both inequalities are strict.
If ma + (n k + 1)b > 1 and m(1 a) = k(1 b) then b = 1 mk (1 a).
Now if we decrease the value of a just a little to a value ~a then b will decrease
by a small amount to a new value ~b = 1 mk (1 ~a), and we can still have
the inequality m~a + (n k + 1)~b > 1. However, this implies that S = M is
44
still a cheapest g-dismantling set with respect to the new weighting with a
dismantling cost of m(1 ~a). Since a > ~a we get that SH(Km;n;1 x) =
m(1 a) < m(1 ~a) SH(Km;n;1 x), a contradiction. Therefore, if
m(1 a) = k(1 b) then ma + (n k + 1)b = 1.
Now if m(1 a) < k(1 b) and ma + (n k + 1)b = 1 then b = 1 man k+1.
If we lower a just a little to a value say ~a then b will increase slightly to a
value ~b and the inequality m(1 ~a) < k(1 ~b) can be maintained. Then we
can actually increase the cost of removing M which will still be a cheapest
dismantling set. We get a contradiction once again, as above.
Since a > 0, then from claim 1 we have that ma + (n k + 1)b = 1 and
m(1 a) = k(1 b) and so we want the a and/or the b that satisfy this system
of equations. Finding both of these values gives us our optimal weighting.
Since ma+(n k+1)b = 1 and m(1 a) = k(1 b) we can solve this system
by rewriting m(1 a) = k(1 b) as m k = ma kb and eliminating the
ma from both equations. This leaves us with 1 + k m = (n + 1)b =) b =
k m+1
n+1 =) k m in this case. Now m(1 a) = k(1 b) = k(1
1+k m
n+1 ) =
k(n k+mn+1 ). However, k(n+m k)n+1 achieves its maximum value 1n+1b(n+m)24 c,
for k 2 f1;::: ;n 1g, at k = bn+m2 c, so SH(Km;n;1 x) = k(n+m k)n+1
1
n+1b
(n+m)2
4 c, contrary to assumption, which nishes this case.
Case 2: S ( N Let jSj = k 2 f1;::: ;n 1g and since S is a cheapest g-dismantling set
then we have that ma+(n k)b < 1 ma+(n k+1)b and k(1 b) m(1 a). We also
may as well assume that SH(Km;n;1 x) = k(1 b) > 1n+1b(n+m)24 c (keeping in mind
that m n < m + 2pm). If we consider the possibility of lowering b to try to exact a
45
slightly higher cheapest dismantling cost, we see that at least one of the two inequalities,
ma + (n k + 1)b 1 and k(1 b) m(1 a) must be equality. Now suppose that
we have ma + (n k + 1)b > 1 and k(1 b) = m(1 a). Then M is also a cheapest
dismantling set, i.e., we are in Case 1, and so we are done in this case. Now suppose
that ma + (n k + 1)b = 1 and k(1 b) < m(1 a). From the equation, we get that
a = 1 (n k+1)bm and so if we lower b, a increases. Pushing b down very slightly, we get new
weights ~b < b and ~a > a so that k(1 ~b) < m(1 ~a) and m~a+ (n k +1)~b = 1. Clearly,
S is still a cheapest g-dismantling set but with a dismantling cost of k(1 ~b) > k(1 b).
This yields a contradiction to the supposition that SH(Km;n;1 x) = k(1 b), and
nishes the disposal of Case 2.
Case 3: S = N We may as well assume that SH(Km;n;1 x) = n(1 b) > 1n+1b(n+m)24 c
(keeping in mind that a > 0 and m n < m+2pm). Since S is a cheapest g-dismantling
set, we have that ma+b 1 and m(1 a) n(1 b). We want to consider the possibility
of lowering b a little in order to exact a higher cheaper dismantling cost. As in previous
cases, it turns out that it must be the case that at least one of the inequalities ma+b 1
and m(1 a) n(1 b) must be equality. Suppose that ma+b = 1 and m(1 a) > n(1 b).
This implies that a = 1 bm and so if we decrease b slightly, we increase a slightly and the
inequality m(1 a) > n(1 b) can still hold. So N is still the cheapest g-dismantling set,
but its new dismantling cost is actually higher than the assumed value of SH(Km;n;1 x)
and so we have a contradiction leading us to the conclusion that b cannot be lowered at
all; and in fact, it must be the case that if ma + b = 1, then m(1 a) = n(1 b).
Therefore, it must be that m(1 a) = n(1 b), which implies that M is also a
cheapest dismantling set, which returns us to case 1 and nishes the proof.
46
4.2 The constant-on-each-part Shields-Harary numbers of Km;n
Let P0(m;n;f) be de ned as SH(Km;n;f) is, except that only weightings con-
stant on each of M;N are allowed. The arguments in [2] show that P0(m;n;f) is
achieved by some such weighting (assuming f is continuous), and Lemma 4.2 guar-
antees that P0(m;n;f) will be achieved with a weight on M less than or equal to
that on N. Proposition 3.3 implies that if f is concave on [0;1] and f(1) = 0 then
P0(m;n;f) = SH(Km;n;f). We will make some general remarks about P0(m;n;f) and
then attempt to calculate if for particular cost functions f, especially f(x) = (1 x)p,
0 < p 1, and f(x) = 1 xp, p 1, since these are concave on [0;1] and f(1) = 0.
Corollary 4.1 shows that as long as f is concave on [0;1] and f(1) = 0 then
P0(m;m;f) = SH0(Km;m;f) and as a direct result, Corollary 4.2 gives the value of
P0(m;m;1 x) = m2m+1. Proposition 4.1 gives the value of P0(m;n;1 x) for all m n.
Now in terms of di erent cost functions, it is not di cult to see that the following
inequalities should hold:
P0(m;n;1 x) P0(m;n;1 xp) where p 1
P0(m;n;1 x) P0(m;n;(1 x)q) where 0 < q 1
In fact, we conclude with the following generalization of these two inequalities.
Proposition 4.2 Let f1(x) and f2(x) be non-increasing, continuous functions on [0;1)
satisfying f1(x) f2(x) for all x 2 [0;1). Then for any of the Shields-Harary parame-
ters P = P(G;f), and any G, P(G;f1) P(G;f2).
Proof. Suppose g is an admissible (depending on how P is de ned) weighting of the
vertices of G and suppose S is a g-dismantling set (of whichever type is called for in
47
the de nition of P) of least cost, with respect to f2. Then S is a g-dismantling set and
X
u2S
f1(g(u))
X
u2S
f2(g(u)). Consequently, the minimum cost of dismantling (g;G) with
respect to f1 is no greater than that of dismantling with respect to f2. Since this holds
for all admissible g, and since P(G;fi) is the supremum of these minimum costs, i = 1;2,
it follows that P(G;f1) P(G;f2).
Corollary 4.3 If f1;f2 are as in the Proposition above, and if f1(x) f2(x) for all
x 2 [0;1], then P0(m;n;f1) P0(m;n;f2).
Proof. In the de nition of P0, only the values of the cost function on [0;1] matter. To
apply Proposition 4.1, extend fi to [0;1) by setting fi(x) = fi(1), for x > 1, i = 1;2.
Corollary 4.4 For 0 < p 1 q, m n < m+2pm, 1n+1b(n+m)24 c min[SH(Km;n;1
xq);SH(Km;n;(1 x)p)], and for n m+2pm, m = min[SH(Km;n;1 xq);SH(Km;n;(1
x)p)].
Proof. In the de nition of SH, only the values of the cost function on [0;1] matter.
1 x 1 xq for q 1 and x 2 [0;1] and 1 x (1 x)p for 0 < p 1 and x 2 [0;1],
thus proving the corollary, for m n < m + 2pm, and proving m min[SH(Km;n;1
xq);SH(Km;n;(1 x)p)] if n > m + 2pm.
By the same argument that was applied in the case f(x) = 1 x, it is easy to see
that for any cost function f satisfying f(0) = 1, f(1) = 0, SH(Km;n;f) m. This
completes the proof of the Corollary.
Bibliography
[1] Andrew Blinco, John Holliday and Sarah Holliday, On the Constant-Weight Shields-
Harary Numbers of Cayley Graphs, Congressus Numerantium 159 (2002) 151-158.
[2] Frank Harary and Peter D. Johnson, Jr., The Shields-Harary Indices of Vulnerability
of a Graph, Mathematical and Computer Modelling (2001), 299-310.
[3] John Holliday and Peter D. Johnson, Jr., The Shields-Harary Numbers of Kn e,
Congressus Numerantium 147 (2001), 153-159.
[4] John Holliday and Peter D. Johnson, Jr., Shields-Harary Numbers of Graphs With
Respect to Continuous Concave Cost Functions, International Journal of Mathemat-
ics and Mathematical Sciences 62, (2003), 3921-3930.
[5] Sarah Holliday and Peter D. Johnson, Jr., On the Constant-Weight Shields-Harary
Numbers of a Tree, Congressus Numerantium 153 (2001), 187-191.
[6] Peter D. Johnson, Jr., A Graph Parameter of Shields and Harary, Congressus Nu-
merantium 82 (1991), 193-200.
[7] Stephen Schanuel, A Combinatorial Problem of Shields and Pearcy, Procedures of the
American Mathematical Society 65 (1977), No. 1, 185-186.
[8] Jared Wunsch, The Shields-Harary Number for Wheel and Broken-Wheel Graphs,
Discrete Applied Mathematics 59 (1995), 193-199.
[9] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ,
1996.
48