GRAPH ENUMERATIONS
Enumeration [ edit ] There is a large literature on graphical enumeration : the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973). Subgraphs, induced subgraphs, and minors [ edit ] A common problem, called the subgraph isomorphism problem , is finding a fixed graph as a subgraph in a given graph. One reason to be interested in such a question is that many graph properties are hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs have it too. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem . For example: Finding the largest complete subgraph is called the clique problem (NP-complete). One special case of subgraph isomorphism is the graph isomorphism problem . It asks whether two graphs are isomorphic. It is not known whether this problem is NP-complete, nor whether...