Power graph analysis

In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory should not be confused with "graphs of functions" and other kinds of graphs.

Please refer to Glossary of graph theory for some basic definitions in graph theory.

History

List structures

Incidence list: The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and possibly weight and other data. Vertices connected by an edge are said to be adjacent.
Adjacency list: Much like the incidence list, each vertex has a list of which vertices it is adjacent to. This causes redundancy in an undirected graph: for example, if vertices A and B are adjacent, A's adjacency list contains B, while B's list contains A. Adjacency queries are faster, at the cost of extra storage space.

Matrix structures

Incidence matrix: The graph is represented by a matrix of size |V| (number of vertices) by |E| (number of edges) where the entry [vertex, edge] contains the edge's endpoint data (simplest case: 1 - connected, 0 - not connected).
Adjacency matrix: This is the n by n matrix A, where n is the number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element $a_{x,y}$ is 1 (or in general the number of xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.
Laplacian matrix or Kirchhoff matrix or Admittance matrix: This is defined as D − A, where D is the diagonal degree matrix. It explicitly contains both adjacency information and degree information.
Distance matrix: A symmetric n by n matrix D whose element $d_{x,y}$ is the length of a shortest path between x and y; if there is no such path $d_{x,y}$ = infinity. It can be derived from powers of A: $d_{x,y}=\min\{n\mid A^{n}[x,y]\neq 0\}.$

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

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

The four-color theorem
The strong perfect graph theorem
The Erdos-Faber-Lovász conjecture (unsolved)
The total coloring conjecture (unsolved)
The list coloring conjecture (unsolved)

References

Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
Pelle, Stéphane (1996), La Théorie des Graphes (PDF), Saint-Mandé: École Nationale des Sciences Géographiques{{citation}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
Chartrand, Gary, Introductory Graph Theory, Dover. ISBN 0-486-24775-9.
Biggs, N.; Lloyd, E. & Wilson, R. Graph Theory, 1736-1936 Oxford University Press, 1986
Harary, Frank, Graph Theory, Addison-Wesley, Reading, MA, 1969.
Harary, Frank, and Palmer, Edgar M., Graphical Enumeration (1973), Academic Press, New York, NY.

External links

Online textbooks

Graph Theory with Applications (1976) by Bondy and Murty
Encyclopaedia Britannica, Graph Theory

Other resources

More people and publications at: Graph Theory Resources
Graph theory tutorial