Browse Theses

A greatest common subgraph (gcs) is a maximum sized subgraph G of every graph in a set ${\cal G}$ of graphs. Sometimes more than one such G can be found for ${\cal G}$ and, hence, the term "gcs" also means the set of all such gcs's for ${\cal G}$. The task of finding the greatest common subgraph of a set of graphs is known to be NP-Hard in general. However, it is an important problem with applications in several fields, including medical compound analysis, object recognition, and information retrieval, and hence is deserving of study. This dissertation represents an attempt to understand the problem by examining subproblems and related problems.

One strategy for dealing with a difficult graph problem is to constrain the domain of the problem to a family, such as trees, in hopes that the problem becomes solvable in polynomial time. This was not the case here, as is demonstrated by a proof of the NP-Completeness of the problem of finding the largest common subgraph of two trees. Nevertheless, trees continued to be a major focus in this research.

A new graphical invariant sn$\sp+$ (additive symmetry number) was developed. Derivations of upper and lower bounds for sn$\sp+$ are presented, as are calculations of sn$\sp+$ for various families of graphs. This invariant motivated the definition and characterization of the so called 1$\sp+$1 trees, an important family which includes paths, full binary trees, stars, and symmetric double stars.

An interest in line graphs in the context of greatest common subgraphs led to the definition of the line greatest common subgraph (linegcs) and variations. Unlike the greatest common subgraph of a set of graphs, which always contain at least one member, the line greatest common subgraph may be empty. However, much can be said about a linegcs or one of its variations. For example, sufficient conditions for a gcs or variation to be a linegcs or variation are presented. Furthermore, a complete characterization of which trees are linegcs or variations of trees, is developed.