Category: Graph invariants

Friendly-index set
In graph theory, a friendly-index set is a finite set of integers associated with a given undirected graph and generated by a type of graph labeling called a friendly labeling. A friendly labeling of
Parry–Sullivan invariant
In mathematics, the Parry–Sullivan invariant (or Parry–Sullivan number) is a numerical quantity of interest in the study of incidence matrices in graph theory, and of certain one-dimensional dynamical
Cutwidth
In graph theory, the cutwidth of an undirected graph G = (V, E) is the smallest integer k with the following property: there is an ordering {v1, …, vn} of the vertices of G, such that for every l = 1,
Linear arboricity
In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic g
Chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was origina
Katz centrality
In graph theory, the Katz centrality of a node is a measure of centrality in a network. It was introduced by Leo Katz in 1953 and is used to measure the relative degree of influence of an actor (or no
Topological index
In the fields of chemical graph theory, molecular topology, and mathematical chemistry, a topological index, also known as a connectivity index, is a type of a molecular descriptor that is calculated
Graph property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the
Radius (graph theory)
No description available.
Tardos function
In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties: * Like the Lovász number of the complement of a gr
Circumference (graph theory)
No description available.
Circuit rank
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break
Vertex connectivity
No description available.
Rank (graph theory)
In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph. * In the matrix theory of graphs the rank r o
Characteristic polynomial of a graph
No description available.
Degree distribution
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees o
Diameter (graph theory)
No description available.
Distinguishing number
No description available.
Edge covering number
No description available.
Szeged index
In chemical graph theory, the Szeged index is a topological index of a molecule, used in biochemistry. The Szeged index, introduced by Iván Gutman, generalizes the concept of the Wiener index introduc
Grundy number
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the g
Betweenness centrality
In graph theory, betweenness centrality (or "betweeness centrality") is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at lea
Intersection number (graph theory)
In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representatio
Matching number
No description available.
Graph pebbling
Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of
Conductance (graph)
In graph theory the conductance of a graph G = (V, E) measures how "well-knit" the graph is: it controls how fast a random walk on G converges to its stationary distribution. The conductance of a grap
Arboricity
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
Lovász number
In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by , using
Randić's molecular connectivity index
The Randić index, also known as the connectivity index, of a graph is the sum of bond contributions where and arethe degrees of the vertices making bond i ~ j.
Vertex covering number
No description available.
Betti number
In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of n-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (
Matching polynomial
In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of the numbers of matchings of various sizes in a
Colin de Verdière graph invariant
Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of
Dimension (graph theory)
In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n
Minimum rank of a graph
In mathematics, the minimum rank is a graph parameter for a graph G. It was motivated by the Colin de Verdière graph invariant.
Degree sequence
No description available.
Entanglement (graph measure)
In graph theory, entanglement of a directed graph is a number measuring how stronglythe cycles of the graph are intertwined. It is defined in terms of a mathematical game in whichn cops try to capture
Girth (graph theory)
In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is define
Bipartite dimension
In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete b
Closeness centrality
In a connected graph, closeness centrality (or closeness) of a node is a measure of centrality in a network, calculated as the reciprocal of the sum of the length of the shortest paths between the nod
Clique number
No description available.
Domination number
No description available.
Pathwidth
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened t
Graph toughness
In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connec
Boxicity
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection gra
Hadwiger number
In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G.Equivalently, the Hadwiger number h(G) is the lar
Graph bandwidth
In graph theory, the graph bandwidth problem is to label the n vertices vi of a graph G with distinct integers so that the quantity is minimized (E is the edge set of G).The problem may be visualized
Order (graph theory)
No description available.
Tree-depth
In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gon
Padmakar–Ivan index
In chemical graph theory, the Padmakar–Ivan (PI) index is a topological index of a molecule, used in biochemistry. The Padmakar–Ivan index is a generalization introduced by and Iván Gutman of the conc
Independent domination number
No description available.
Wiener index
In chemical graph theory, the Wiener index (also Wiener number) introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pa
Graph genus
No description available.
Perron number
In mathematics, a Perron number is an algebraic integer α which is real and exceeds 1, but such that its conjugate elements are all less than α in absolute value. For example, the larger of the two ro
Cheeger constant (graph theory)
In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of
Strength of a graph
In the branch of mathematics called graph theory, the strength of an undirected graph corresponds to the minimum ratio edges removed/components created in a decomposition of the graph in question. It
Clique-width
In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for
Twin-width
The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is t
Hosoya index
The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for thi
Thue number
In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by and named after mathematician Axel Thue, who studied the squarefree words used to
Sparsity matroid
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the numb
Fractional chromatic number
No description available.
Algebraic connectivity
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph G is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the L
(a, b)-decomposition
In graph theory, the (a, b)-decomposition of an undirected graph is a partition of its edges into a + 1 sets, each one of them inducing a forest, except one which induces a graph with maximum degree b
Degeneracy (graph theory)
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.
Estrada index
In chemical graph theory, the Estrada index is a topological index of protein folding. The index was first defined by Ernesto Estrada as a measure of the degree of folding of a protein, which is repre
Independence number
No description available.
Edge chromatic number
No description available.
Dissociation number
In the mathematical discipline of graph theory, a subset of vertices in a graph G is called dissociation if it induces a subgraph with maximum degree 1. The number of vertices in a maximum cardinality
Crossing number (graph theory)
In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is
Thickness (graph theory)
In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having th
Average path length
Average path length, or average shortest path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes. I
Queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of
Cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi. Intuitively, this concept measures how close adigraph is to a directed acyclic
Matching preclusion
In graph theory, a branch of mathematics, the matching preclusion number of a graph G (denoted mp(G)) is the minimum number of edges whose deletion results in the destruction of a perfect matching or
Bondage number
In the mathematical field of graph theory, the bondage number of a nonempty graph is the cardinality of the smallest set E of edges such that the domination number of the graph with the edges E remove
Vizing's conjecture
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing, and states that, if γ(G
Domatic number
In graph theory, a domatic partition of a graph is a partition of into disjoint sets , ,..., such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph;
Splittance
In graph theory, a branch of mathematics, the splittance of an undirected graph measures its distance from a split graph. A split graph is a graph whose vertices can be partitioned into an independent
Slope number
In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as point
Branch-decomposition
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 an
Genus (mathematics)
In mathematics, genus (plural genera) has a few different, but closely related, meanings. Intuitively, the genus is the number of "holes" of a surface. A sphere has genus 0, while a torus has genus 1.
Periodic graph (graph theory)
In graph theory, a branch of mathematics, a periodic graph with respect to an operator F on graphs is one for which there exists an integer n > 0 such that Fn(G) is isomorphic to G. For example, every
Clustering coefficient
In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social ne
Graph polynomial
In mathematics, a graph polynomial is a graph invariant whose values are polynomials. Invariants of this type are studied in algebraic graph theory.Important graph polynomials include: * The characte
Meshedness coefficient
In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar
Tutte–Grothendieck invariant
In mathematics, a Tutte–Grothendieck (TG) invariant is a type of graph invariant that satisfies a generalized deletion–contraction formula. Any evaluation of the Tutte polynomial would be an example o
Treewidth
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
Chromatic number
No description available.
Cop number
In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pu
Shannon capacity of a graph
In graph theory, the Shannon capacity of a graph is a graph invariant defined from the number of independent sets of strong graph products. It is named after American mathematician Claude Shannon. It
Strahler number
In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity. These numbers were first developed in hydrology by Robert E. Ho
Metric dimension (graph theory)
In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Fi
Size (graph theory)
No description available.
Hyper-Wiener index
In chemical graph theory, the hyper-Wiener index or hyper-Wiener number is a topological index of a molecule, used in biochemistry. The hyper-Wiener index is a generalization introduced by Milan Randi