# Category:Graph theory

Here is a list of articles in the Graph theory category of the Computing portal that unifies foundations of mathematics and computations using computers.
**Graph theory** is the branch of mathematics that examines the properties of **mathematical graphs**. See glossary of graph theory for common terms and their definition.

Informally, this type of graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs), which can also have associated directions. Typically, a graph is depicted as a set of dots (i.e., vertices) connected by lines (i.e., edges), with an arrowhead on a line representing a directed arc.

Such graphs can be used to represent and analyze a variety of systems and problems, including colorability problems, shortest path algorithms and spanning trees.

For information on other types of graphs see graph (disambiguation).

## Subcategories

This category has the following 21 subcategories, out of 21 total.

### A

### C

### D

### E

### G

### I

### M

### N

### O

### R

### T

## Pages in category "Graph theory"

The following 115 pages are in this category, out of 115 total.

- Graph theory
*(computing)*

### *

- List of graph theory topics
*(computing)*

### A

- Aanderaa–Karp–Rosenberg conjecture
*(computing)*

### B

- Bicircular matroid
*(computing)*

### C

- Calculus on finite weighted graphs
*(computing)* - Centrality
*(computing)* - Chip-firing game
*(computing)* - Graph coloring
*(computing)* - Consensus dynamics
*(computing)* - Convex subgraph
*(computing)* - Copying mechanism
*(computing)* - Copying network models
*(computing)* - Covering graph
*(computing)* - Cycle decomposition (graph theory)
*(computing)*

### D

- Deficiency (graph theory)
*(computing)* - Degree (graph theory)
*(computing)* - Degree distribution
*(computing)* - Deletion–contraction formula
*(computing)* - Dense subgraph
*(computing)* - Directed graph
*(computing)* - Discharging method (discrete mathematics)
*(computing)* - Discrete Laplace operator
*(computing)* - Distance (graph theory)
*(computing)* - Distance oracle
*(computing)* - Dominator (graph theory)
*(computing)* - Dot product representation of a graph
*(computing)*

### E

- Eigenvector centrality
*(computing)* - Erdős–Burr conjecture
*(computing)* - Erdős–Gyárfás conjecture
*(computing)* - Erdős–Hajnal conjecture
*(computing)* - Erdős on Graphs
*(computing)* - Expander mixing lemma
*(computing)*

### F

- Five room puzzle
*(computing)* - Forbidden graph characterization
*(computing)* - Fractional graph isomorphism
*(computing)* - Frequency partition of a graph
*(computing)* - Friedman's SSCG function
*(computing)* - Friendship paradox
*(computing)*

### G

- Glossary of graph theory terms
*(computing)* - Goldberg–Seymour conjecture
*(computing)* - Graph (abstract data type)
*(computing)* - Graph (discrete mathematics)
*(computing)* - Graph algebra
*(computing)* - Graph amalgamation
*(computing)* - Graph canonization
*(computing)* - Graph dynamical system
*(computing)* - Graph edit distance
*(computing)* - Graph entropy
*(computing)* - Graph equation
*(computing)* - Graph Fourier Transform
*(computing)* - Graph homomorphism
*(computing)* - Graph isomorphism
*(computing)* - Graph property
*(computing)* - Graph removal lemma
*(computing)* - GraphCrunch
*(computing)* - Graphon
*(computing)*

### H

- Hall violator
*(computing)* - Handshaking lemma
*(computing)* - Hereditary property
*(computing)* - Hierarchical closeness
*(computing)* - Homeomorphism (graph theory)
*(computing)* - Homomorphic equivalence
*(computing)* - Hypergraph removal lemma
*(computing)*

### I

- Icosian calculus
*(computing)* - Icosian game
*(computing)* - Implicit graph
*(computing)* - Incidence poset
*(computing)*

### L

- Logic of graphs
*(computing)* - Loop (graph theory)
*(computing)* - Lovász conjecture
*(computing)*

### M

- Magic graph
*(computing)* - Markov chain
*(computing)* - Matching in hypergraphs
*(computing)* - The Mathematics of Chip-Firing
*(computing)* - Maximally-matchable edge
*(computing)* - Maximum cardinality matching
*(computing)* - Mediation-driven attachment model
*(computing)* - Mixed graph
*(computing)* - Multi-level technique
*(computing)* - Multi-trials technique
*(computing)*

### N

- Nash-Williams theorem
*(computing)* - Network theory
*(computing)* - New digraph reconstruction conjecture
*(computing)* - Node influence metric
*(computing)* - Null model
*(computing)* - Nullity (graph theory)
*(computing)*

### O

- Oberwolfach problem
*(computing)*

### P

- Parallel single-source shortest path algorithm
*(computing)* - Pearls in Graph Theory
*(computing)* - The Petersen Graph
*(computing)* - Phase-field models on graphs
*(computing)* - Pseudorandom graph
*(computing)* - Pósa's theorem
*(computing)*

### Q

- Quasi-random graph
*(computing)*

### R

- Random cluster model
*(computing)* - Random graph
*(computing)* - Random walk closeness centrality
*(computing)* - Reconstruction conjecture
*(computing)* - Resistance distance
*(computing)* - Ryser's conjecture
*(computing)*

### S

- Second neighborhood problem
*(computing)* - Semantic Brand Score
*(computing)* - Sequential dynamical system
*(computing)* - Seven Bridges of Königsberg
*(computing)* - Sidorenko's conjecture
*(computing)* - Single-entry single-exit
*(computing)* - Spatial network
*(computing)* - Structural induction
*(computing)* - Sumner's conjecture
*(computing)* - Szymanski's conjecture
*(computing)*

### T

- Transitive reduction
*(computing)*

### V

- Vertex (graph theory)
*(computing)* - Vertex cover in hypergraphs
*(computing)* - Vertex k-center problem
*(computing)*

### W

- Weighted planar stochastic lattice
*(computing)*