0.7 Graphs  (Page 3/21)

• Laplacian matrix or Kirchhoff matrix or Admittance matrix - is defined as degree matrix minus adjacency matrix and thus contains adjacency information and degree information about the vertices

• Distance matrix - A symmetric N by N matrix an element Mx,y of which is the length of shortest path between x and y; if there is no such path Mx,y = infinity. It can be derived from powers of the Adjacency matrix.

Problems in graph theory

Enumeration

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

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, or all induced subgraphs, have it too. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem.

• Finding the largest complete graph is called the clique problem (NP-complete).

A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example,

• Finding the largest edgeless induced subgraph, or independent set, called the independent set problem (NP-complete).

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. A famous example:

• A graph is planar if it contains as a minor neither the complete bipartite graph K3,3 (See the Three cottage problem) nor the complete graph K5.

Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs, for example:

• The reconstruction conjecture

Graph coloring

Many problems have to do with various ways of coloring graphs, for example:

• The four-color theorem
• The strong perfect graph theorem
• The Erdős-Faber-Lovász conjecture (unsolved)
• The total coloring conjecture (unsolved)
• The list coloring conjecture (unsolved)

Route problems

• Hamiltonian path and cycle problems
• Minimum spanning tree
• Route inspection problem (also called the "Chinese Postman Problem")
• Seven Bridges of Königsberg
• Shortest path problem
• Steiner tree
• Three cottage problem
• Traveling salesman problem (NP-Complete)

Network flow

There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:

Visibility graph problems