- FindStat

Identifier

Mp00324: Graphs —chromatic difference sequence⟶ Integer compositions
Mp00184: Integer compositions —to threshold graph⟶ Graphs
St000351: Graphs ⟶ ℤ

Values

([],1) => [1] => ([],1) => 0

([],2) => [2] => ([],2) => 0

([(0,1)],2) => [1,1] => ([(0,1)],2) => -1

([],3) => [3] => ([],3) => 0

([(1,2)],3) => [2,1] => ([(0,2),(1,2)],3) => 0

([(0,2),(1,2)],3) => [2,1] => ([(0,2),(1,2)],3) => 0

([(0,1),(0,2),(1,2)],3) => [1,1,1] => ([(0,1),(0,2),(1,2)],3) => 2

([],4) => [4] => ([],4) => 0

([(2,3)],4) => [3,1] => ([(0,3),(1,3),(2,3)],4) => 0

([(1,3),(2,3)],4) => [3,1] => ([(0,3),(1,3),(2,3)],4) => 0

([(0,3),(1,3),(2,3)],4) => [3,1] => ([(0,3),(1,3),(2,3)],4) => 0

([(0,3),(1,2)],4) => [2,2] => ([(1,3),(2,3)],4) => 0

([(0,3),(1,2),(2,3)],4) => [2,2] => ([(1,3),(2,3)],4) => 0

([(1,2),(1,3),(2,3)],4) => [2,1,1] => ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 0

([(0,3),(1,2),(1,3),(2,3)],4) => [2,1,1] => ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 0

([(0,2),(0,3),(1,2),(1,3)],4) => [2,2] => ([(1,3),(2,3)],4) => 0

([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => [2,1,1] => ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 0

([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => [1,1,1,1] => ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => -3

([],5) => [5] => ([],5) => 0

([(3,4)],5) => [4,1] => ([(0,4),(1,4),(2,4),(3,4)],5) => 0

([(2,4),(3,4)],5) => [4,1] => ([(0,4),(1,4),(2,4),(3,4)],5) => 0

([(1,4),(2,4),(3,4)],5) => [4,1] => ([(0,4),(1,4),(2,4),(3,4)],5) => 0

([(0,4),(1,4),(2,4),(3,4)],5) => [4,1] => ([(0,4),(1,4),(2,4),(3,4)],5) => 0

([(1,4),(2,3)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(1,4),(2,3),(3,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(0,1),(2,4),(3,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,4),(2,3),(3,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(1,4),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(1,3),(1,4),(2,3),(2,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [3,1,1] => ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,3),(2,3),(2,4)],5) => [3,2] => ([(1,4),(2,4),(3,4)],5) => 0

([(0,1),(2,3),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [2,1,1,1] => ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [2,1,1,1] => ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [2,1,1,1] => ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => [2,2,1] => ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [2,1,1,1] => ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 0

([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => [1,1,1,1,1] => ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([],6) => [6] => ([],6) => 0

([(4,5)],6) => [5,1] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0

([(3,5),(4,5)],6) => [5,1] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0

([(2,5),(3,5),(4,5)],6) => [5,1] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,5),(2,5),(3,5),(4,5)],6) => [5,1] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => [5,1] => ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 0

([(2,5),(3,4)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(2,5),(3,4),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,2),(3,5),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,1),(2,5),(3,5),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(2,4),(2,5),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,4),(3,4)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => [4,1,1] => ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(2,3)],6) => [3,3] => ([(2,5),(3,5),(4,5)],6) => 0

([(1,5),(2,4),(3,4),(3,5)],6) => [4,2] => ([(1,5),(2,5),(3,5),(4,5)],6) => 0

([(0,1),(2,5),(3,4),(4,5)],6) => [3,3] => ([(2,5),(3,5),(4,5)],6) => 0

([(1,2),(3,4),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => [3,3] => ([(2,5),(3,5),(4,5)],6) => 0

([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => [3,3] => ([(2,5),(3,5),(4,5)],6) => 0

([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => [3,2,1] => ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 0

>>> Load all 1252 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The determinant of the adjacency matrix of a graph.
For a labelled graph $G$ with vertices $\{1,\ldots,n\}$, the adjacency matrix is the matrix $(a_{ij})$ with $a_{ij} = 1$ if the vertices $i$ and $j$ are joined by an edge in $G$.
Since the determinant is invariant under simultaneous row and column permutations, the determinant of the adjacency is well-defined for an unlabelled graph.
According to [2], Equation 8, this determinant can be computed as follows: let $s(G)$ be the number of connected components of $G$ that are cycles and $r(G)$ the number of connected components that equal $K_2$. Then $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs $H$ of $G$ that have as connected components only $K_2$'s and cycles.

Map

chromatic difference sequence

Description

The chromatic difference sequence of a graph.
Let $G$ be a simple graph with chromatic number $\kappa$. Let $\alpha_m$ be the maximum number of vertices in a $m$-colorable subgraph of $G$. Set $\delta_m=\alpha_m-\alpha_{m-1}$. The sequence $\delta_1,\delta_2,\dots\delta_\kappa$ is the chromatic difference sequence of $G$.
All entries of the chromatic difference sequence are positive: $\alpha_m > \alpha_{m-1}$ for $m < \kappa$, because we can assign any uncolored vertex of a partial coloring with $m-1$ colors the color $m$. Therefore, the chromatic difference sequence is a composition of the number of vertices of $G$ into $\kappa$ parts.

Map

to threshold graph

Description

The threshold graph corresponding to the composition.
A threshold graph is a graph that can be obtained from the empty graph by adding successively isolated and dominating vertices.
A threshold graph is uniquely determined by its degree sequence.
The Laplacian spectrum of a threshold graph is integral. Interpreting it as an integer partition, it is the conjugate of the partition given by its degree sequence.