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
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.
- Hits: 84