Network Evolution: Bugs, Superbugs, and Graph Infections

Abstract

In this paper we describe types of evolutions of networks (modelled as graphs) by analyzing the compositions between Hamiltonian graphs and graph “bugs”. We identify one type of “superbug”: a bug structure that can destroy the Hamiltonicity of a graph (and thus render a potentially-optimal delivery network inefficient), and also describe types of graphbug infections and their effects.

Keywords

• hamiltonian graphs
• non-hamiltonian graphs
• bugs
• a-links
• b-links.