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