Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called arcs, links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For other uses, see Graph (disambiguation).

$V$ , a of vertices (also called nodes or points);

set

$E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}$ , a of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with two distinct vertices).

set

Problems[edit]

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:

Bender, Edward A.; Williamson, S. Gill (2010). .

Lists, Decisions and Graphs. With an Introduction to Probability

Berge, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod. 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.

Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. Oxford University Press.

Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Springer. 978-1-84628-969-9.

ISBN

Bollobás, Béla; Riordan, O. M. (2003). Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) (1st ed.). Weinheim: Wiley VCH.

Chartrand, Gary (1985). . Dover. ISBN 0-486-24775-9.

Introductory Graph Theory

Deo, Narsingh (1974). (PDF). Englewood, New Jersey: Prentice-Hall. ISBN 0-13-363473-6. Archived (PDF) from the original on 2019-05-17.

Graph Theory with Applications to Engineering and Computer Science

Gibbons, Alan (1985). Algorithmic Graph Theory. .

Cambridge University Press

Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. .

Academic Press

Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley.

Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. New York, New York: Academic Press.

Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. .

North-Holland

Newman, Mark (2010). Networks: An Introduction. Oxford University Press.

Kepner, Jeremy; Gilbert, John (2011). . Philadelphia, Pennsylvania: SIAM. ISBN 978-0-898719-90-1.

Graph Algorithms in The Language of Linear Algebra

, Encyclopedia of Mathematics, EMS Press, 2001 [1994]

"Graph theory"

Archived 2012-01-16 at the Wayback Machine

Graph theory tutorial

A searchable database of small connected graphs

at the Wayback Machine (archived February 6, 2006)

Image gallery: graphs

Concise, annotated list of graph theory resources for researchers

— a graph theory IDE

rocs

— non-technical paper discussing graphs of people and computers

The Social Life of Routers

— tools to teach and learn graph theory

Graph Theory Software

and library resources in your library and in other libraries about graph theory

Online books

Archived 2019-07-13 at the Wayback Machine with references and links to graph library implementations