On Maximizing the Number of Specified Subgraphs of Order Three in a Graph

Prof. Ashok Amin

Computer Science Department
University of Alabama in Huntsville

April 6, 2001

Abstract

Consider graphs in which either edges or vertices are operational with fixed probability p and p is close to zero. Graphs which are most reliable with respect to global or pair-connected reliability maximize the number of appropriate subgraphs on three vertices. Thus, the problems of maximizing specified subgraphs of order three in a graph are of interest. We will review progress on the problems when the subgraphs of interest are paths (not necessarily induced), connected subgraphs, and induced paths on three vertices.