Title

On the Edge-Integrity of Some Graphs and Their Complements

Document Type

Article

Publication Date

11-15-1993

Department

Mathematics

Abstract

In this paper the authors study the edge-integrity of graphs. Edge-integrity is a very useful measure of the vulnerability of a network, in particular a communication network, to disruption through the deletion of edges. A number of problems are examined, including some Nordhaus-Gaddum type results. Honest graphs, i.e. those which have the maximum possible edge-integrity, are also investigated. A number of interesting open problems are also posed.

Publication Title

Discrete Mathematics

Volume

122

Issue

1-3

First Page

245

Last Page

253