A connected graph G is defined to be k-1-insensitive if the domination number 1(G) is unchanged when an arbitrary set of k edges is removed. The problem has been solved fork= 1. This Ph.D. dissertation focuses on finding extremal k-1-insensitive graphs on p nodes, fork~ 2. A graph is extremal if it has the minimum number of edges. Two subproblems are considered. The first, which has been solved completely, specifies that the same set of nodes dominates each graph obtained from G by removing k edges. The second requires only that the graph G be connected. This is a much more difficult problem and represents the area of major contribution. Asymptotically correct values for the minimum number of edges e have been found for all k ~ 2 and all 1 ~ 2 by establishing lower and upper bounds fore. The difference in these bounds is 0(1k) and is independent of p. The general results are improved when k 2 and 1 ~ 3, and exact solutions are given when k - 1 = 2 and when 1 1 ii with k arbitrary. Considering applications for k-~-insensitive graphs, we introduce the G-network, a new topological design which is a suitable architecture for point-to-point and interconnection networks. We show that the G-network has the following desirable characteristics: efficient routing, simple connections, small number of links and fault tolerance. Significant improvement in terms of routing performance and the number of edges is shown when the G-network is compared to the popular Barrel Shifter, Illiac and Hypercube networks. iii
Brigham, Robert C.
Doctor of Philosophy (Ph.D.)
College of Arts and Sciences
Length of Campus-only Access
Doctoral Dissertation (Open Access)
Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences
Rice, Teresa Haynes, "On K - Y - insensitive donimation" (1988). Retrospective Theses and Dissertations. 4331.