Abstract

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

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

1988

Semester

Summer

Advisor

Brigham, Robert C.

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

236 p.

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0025764

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Accessibility Status

Searchable text

Download

Share

COinS