searching the database
Your data matches 59 different statistics following compositions of up to 3 maps.
(click to perform a complete search on your data)
(click to perform a complete search on your data)
Matching statistic: St000171
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The degree of the graph.
This is the maximal vertex degree of a graph.
Matching statistic: St000272
(load all 3 compositions to match this statistic)
(load all 3 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The treewidth of a graph.
A graph has treewidth zero if and only if it has no edges. A connected graph has treewidth at most one if and only if it is a tree. A connected graph has treewidth at most two if and only if it is a series-parallel graph.
Matching statistic: St000454
(load all 2 compositions to match this statistic)
(load all 2 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The largest eigenvalue of a graph if it is integral.
If a graph is $d$-regular, then its largest eigenvalue equals $d$. One can show that the largest eigenvalue always lies between the average degree and the maximal degree.
This statistic is undefined if the largest eigenvalue of the graph is not integral.
Matching statistic: St000536
(load all 3 compositions to match this statistic)
(load all 3 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The pathwidth of a graph.
Matching statistic: St000537
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The cutwidth of a graph.
This is the minimum possible width of a linear ordering of its vertices, where the width of an ordering $\sigma$ is the maximum, among all the prefixes of $\sigma$, of the number of edges that have exactly one vertex in a prefix.
Matching statistic: St001270
(load all 2 compositions to match this statistic)
(load all 2 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The bandwidth of a graph.
The bandwidth of a graph is the smallest number $k$ such that the vertices of the graph can be
ordered as $v_1,\dots,v_n$ with $k \cdot d(v_i,v_j) \geq |i-j|$.
We adopt the convention that the singleton graph has bandwidth $0$, consistent with the bandwith of the complete graph on $n$ vertices having bandwidth $n-1$, but in contrast to any path graph on more than one vertex having bandwidth $1$. The bandwidth of a disconnected graph is the maximum of the bandwidths of the connected components.
Matching statistic: St001277
(load all 3 compositions to match this statistic)
(load all 3 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The degeneracy of a graph.
The degeneracy of a graph $G$ is the maximum of the minimum degrees of the (vertex induced) subgraphs of $G$.
Matching statistic: St001358
(load all 2 compositions to match this statistic)
(load all 2 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The largest degree of a regular subgraph of a graph.
For $k > 2$, it is an NP-complete problem to determine whether a graph has a $k$-regular subgraph, see [1].
Matching statistic: St001644
(load all 2 compositions to match this statistic)
(load all 2 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The dimension of a graph.
The dimension of a graph is the least integer $n$ such that there exists a representation of the graph in the Euclidean space of dimension $n$ with all vertices distinct and all edges having unit length. Edges are allowed to intersect, however.
Matching statistic: St001792
(load all 3 compositions to match this statistic)
(load all 3 compositions to match this statistic)
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0
[[3,3,1],[1,1]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,3,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2],[3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,2,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,2,1,1],[2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,3,2,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2],[2]]
=> ([(1,2),(1,3),(2,4),(3,4)],5)
=> ([(1,3),(1,4),(2,3),(2,4)],5)
=> 2
[[5,4,2],[4,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,1,1],[3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,2,1],[4,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,1],[3,3,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,1],[4,3,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,4,3,2],[3,3,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2],[3,2,2]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[5,4,3,2],[4,3,2]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,3,2,2,1],[2,2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[3,3,2,1,1],[2,2,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,4,3,2,1],[3,3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[3,2,2,1,1],[2,1,1]]
=> ([(1,4),(2,3)],5)
=> ([(1,4),(2,3)],5)
=> 1
[[4,3,3,2,1],[3,2,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,2,1],[3,2,1,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[4,3,2,1,1],[3,2,1]]
=> ([(3,4)],5)
=> ([(3,4)],5)
=> 1
[[5,4,3,2,1],[4,3,2,1]]
=> ([],5)
=> ([],5)
=> 0
[[4,4,2],[2,2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,2,2],[2]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[6,4,2],[4,2]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
[[3,3,1,1],[1,1]]
=> ([(0,4),(1,2),(1,3),(2,5),(3,5)],6)
=> ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[4,4,2,1],[2,2,1]]
=> ([(2,3),(2,4),(3,5),(4,5)],6)
=> ([(2,4),(2,5),(3,4),(3,5)],6)
=> 2
[[5,3,1,1],[3,1]]
=> ([(0,5),(1,4),(2,3)],6)
=> ([(0,5),(1,4),(2,3)],6)
=> 1
Description
The arboricity of a graph.
This is the minimum number of forests that covers all edges of the graph.
The following 49 statistics, ordered by result quality, also match your data. Click on any of them to see the details.
St001962The proper pathwidth of a graph. St000147The largest part of an integer partition. St000786The maximal number of occurrences of a colour in a proper colouring of a graph. St001093The detour number of a graph. St001580The acyclic chromatic number of a graph. St001674The number of vertices of the largest induced star graph in the graph. St001720The minimal length of a chain of small intervals in a lattice. St001883The mutual visibility number of a graph. St001963The tree-depth of a graph. St001587Half of the largest even part of an integer partition. St000010The length of the partition. St000381The largest part of an integer composition. St000382The first part of an integer composition. St000676The number of odd rises of a Dyck path. St000734The last entry in the first row of a standard tableau. St000808The number of up steps of the associated bargraph. St001494The Alon-Tarsi number of a graph. St001592The maximal number of simple paths between any two different vertices of a graph. St001039The maximal height of a column in the parallelogram polyomino associated with a Dyck path. St000172The Grundy number of a graph. St001029The size of the core of a graph. St001108The 2-dynamic chromatic number of a graph. St001116The game chromatic number of a graph. St000093The cardinality of a maximal independent set of vertices of a graph. St000097The order of the largest clique of the graph. St000098The chromatic number of a graph. St001291The number of indecomposable summands of the tensor product of two copies of the dual of the Nakayama algebra associated to a Dyck path. St000845The maximal number of elements covered by an element in a poset. St000846The maximal number of elements covering an element of a poset. St000528The height of a poset. St001343The dimension of the reduced incidence algebra of a poset. St000640The rank of the largest boolean interval in a poset. St001337The upper domination number of a graph. St001338The upper irredundance number of a graph. St000080The rank of the poset. St000299The number of nonisomorphic vertex-induced subtrees. St000822The Hadwiger number of the graph. St001330The hat guessing number of a graph. St001642The Prague dimension of a graph. St001331The size of the minimal feedback vertex set. St001512The minimum rank of a graph. St000453The number of distinct Laplacian eigenvalues of a graph. St000777The number of distinct eigenvalues of the distance Laplacian of a connected graph. St000455The second largest eigenvalue of a graph if it is integral. St001323The independence gap of a graph. St001318The number of vertices of the largest induced subforest with the same number of connected components of a graph. St001321The number of vertices of the largest induced subforest of a graph. St000264The girth of a graph, which is not a tree. St001738The minimal order of a graph which is not an induced subgraph of the given graph.
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!