Graph invariants

topological property

characteristic of a graph

length of a shortest cycle contained in a graph

number defined from a node-link network quantifying how likely it is that two neighbors of a randomly chosen node will be adjacent

measure of the branching complexity of a mathematical tree or a river system

used to distinguish topological spaces based on the connectivity of n-dimensional simplicial complexes

polynomial defined from a node-link graph, that counts the number of graph colorings as a function of the number of colors

probability distribution of degrees of a node over the whole network

the minimum number of edges to remove from a graph to eliminate all its cycles

network measure

intrinsic property of undirected graphs

the smallest number of edge crossings possible in a drawing of a node-link graph

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called -trees, and the graphs with treewidth at most are called partial -trees. Many other well-studied graph families also have bounded treewidth.

measure of graph sparsity

isomorphism-invariant property of graphs

thumb|upright=1.35|Construction of a distance-hereditary graph of clique-width 3 by disjoint unions, relabelings, and label-joins. Vertex labels are shown as colors.

In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition is a sequence of subsets of vertices of such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness (one less than the maximum clique size

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

In the mathematical field of graph theory, the boxicity of a graph is a graph invariant defined to be the minimum dimension of Euclidean space required to represent the graph as an intersection graph of axis-parallel closed boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and these boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.

type of a molecular descriptor that is calculated based on the molecular graph of a chemical compound. Topological indices are numerical parameters of a graph which characterize its topology and are usually graph invariant

algebraic encoding of graph connectivity

second-smallest eigenvalue of a graph Laplacian

minimum number of planar graphs into which the edges can be partitioned

thumb|upright=1.35|Branch decomposition of a grid graph, showing an e-separation. The separation, the decomposition, and the graph all have width three. In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposi

size of an independent set of graph vertices of maximal size

nonincreasing sequence of vertex degrees

graph invariant

graph invariant

longest distance between two vertices in a graph

nonnegative-rational-valued invariant of undirected finite graphs; graph-theoretic analogue of the Cheeger constant for compact Riemannian manifolds

graph connectivity property

graph property