On viruses in graphs and digraphs

Abstract:

A virus is a local configuration that, if present in a graph or a digraph, forbids these graphs or digraphs to have a specific property. The aim of this article is to sketch the evolution of the virus theory from its birth in 1991. Moreover some new results and open questions are given. The properties with its known viruses, that will be discussed in this work, are the following: hamiltonian, traceable, fc-connected, fc-edge-connected, strongly connected and have a perfect matching.

Año de publicación:

2008

Keywords:

• virus
• Graph property
• Digraph property
• graph
• Digraph

Fuente:

scopus

google