On the Edge-Integrity of Some Graphs and Their Complements
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.
Piazza, B. L.
(1993). On the Edge-Integrity of Some Graphs and Their Complements. Discrete Mathematics, 122(1-3), 245-253.
Available at: http://aquila.usm.edu/fac_pubs/6686