Processing math: 46%

Your data matches 148 different statistics following compositions of up to 3 maps.
(click to perform a complete search on your data)
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St000172: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The Grundy number of a graph. The Grundy number Γ(G) is defined to be the largest k such that G admits a greedy k-coloring. Any order of the vertices of G induces a greedy coloring by assigning to the i-th vertex in this order the smallest positive integer such that the partial coloring remains a proper coloring. In particular, we have that χ(G)Γ(G)Δ(G)+1, where χ(G) is the chromatic number of G ([[St000098]]), and where Δ(G) is the maximal degree of a vertex of G ([[St000171]]).
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St000918: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The 2-limited packing number of a graph. A subset B of the set of vertices of a graph is a k-limited packing set if its intersection with the (closed) neighbourhood of any vertex is at most k. The k-limited packing number is the largest number of vertices in a k-limited packing set.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St001116: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The game chromatic number of a graph. Two players, Alice and Bob, take turns colouring properly any uncolored vertex of the graph. Alice begins. If it is not possible for either player to colour a vertex, then Bob wins. If the graph is completely colored, Alice wins. The game chromatic number is the smallest number of colours such that Alice has a winning strategy.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St001304: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The number of maximally independent sets of vertices of a graph. An '''independent set''' of vertices of a graph is a set of vertices no two of which are adjacent. If a set of vertices is independent then so is every subset. This statistic counts the number of maximally independent sets of vertices.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St001581: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The achromatic number of a graph. This is the maximal number of colours of a proper colouring, such that for any pair of colours there are two adjacent vertices with these colours.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St001670: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The connected partition number of a graph. This is the maximal number of blocks of a set partition P of the set of vertices of a graph such that contracting each block of P to a single vertex yields a clique. Also called the pseudoachromatic number of a graph. This is the largest n such that there exists a (not necessarily proper) n-coloring of the graph so that every two distinct colors are adjacent.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St001963: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 2
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 2
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 2
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 2
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 2
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 2
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 2
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 3
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 3
Description
The tree-depth of a graph. The tree-depth td(G) of a graph G whose connected components are G1,,Gp is recursively defined as td(G)={1,if |G|=11+min Nešetřil and Ossona de Mendez [2] proved that the tree-depth of a connected graph is equal to its minimum elimination tree height and its centered chromatic number (fewest colors needed for a vertex coloring where every connected induced subgraph has a color that appears exactly once). Tree-depth is strictly greater than [[St000536|pathwidth]]. A [[St001120|longest path]] in G has at least \operatorname{td}(G) vertices [3].
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St000260: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 0 = 1 - 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 1 = 2 - 1
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 1 = 2 - 1
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
Description
The radius of a connected graph. This is the minimum eccentricity of any vertex.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St000362: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 0 = 1 - 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 1 = 2 - 1
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 1 = 2 - 1
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
Description
The size of a minimal vertex cover of a graph. A '''vertex cover''' of a graph G is a subset S of the vertices of G such that each edge of G contains at least one vertex of S. Finding a minimal vertex cover is an NP-hard optimization problem.
Mp00061: Permutations to increasing treeBinary trees
Mp00011: Binary trees to graphGraphs
St000387: Graphs ⟶ ℤResult quality: 100% values known / values provided: 100%distinct values known / distinct values provided: 100%
Values
[1] => [.,.]
=> ([],1)
=> 0 = 1 - 1
[1,2] => [.,[.,.]]
=> ([(0,1)],2)
=> 1 = 2 - 1
[2,1] => [[.,.],.]
=> ([(0,1)],2)
=> 1 = 2 - 1
[1,2,3] => [.,[.,[.,.]]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,3,2] => [.,[[.,.],.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,1,3] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[2,3,1] => [[.,[.,.]],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,1,2] => [[.,.],[.,.]]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[3,2,1] => [[[.,.],.],.]
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[1,2,3,4] => [.,[.,[.,[.,.]]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3] => [.,[.,[[.,.],.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,3,2,4] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,3,4,2] => [.,[[.,[.,.]],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,4,2,3] => [.,[[.,.],[.,.]]]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[1,4,3,2] => [.,[[[.,.],.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,3,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,1,4,3] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,1,4] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,3,4,1] => [[.,[.,[.,.]]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,1,3] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[2,4,3,1] => [[.,[[.,.],.]],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,2,4] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,1,4,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,1,4] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,2,4,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[3,4,1,2] => [[.,[.,.]],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[3,4,2,1] => [[[.,[.,.]],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,2,3] => [[.,.],[.,[.,.]]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,1,3,2] => [[.,.],[[.,.],.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,1,3] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,2,3,1] => [[[.,.],[.,.]],.]
=> ([(0,3),(1,3),(2,3)],4)
=> 1 = 2 - 1
[4,3,1,2] => [[[.,.],.],[.,.]]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[4,3,2,1] => [[[[.,.],.],.],.]
=> ([(0,3),(1,2),(2,3)],4)
=> 2 = 3 - 1
[1,2,4,3,5] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,2,5,3,4] => [.,[.,[[.,.],[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,4,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,2,5,4] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,4,2,5] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,3,5,2,4] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,3,5] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,2,5,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,2,5] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,3,5,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,4,5,2,3] => [.,[[.,[.,.]],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,3,4] => [.,[[.,.],[.,[.,.]]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,2,4,3] => [.,[[.,.],[[.,.],.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,2,4] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,3,4,2] => [.,[[[.,.],[.,.]],.]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[1,5,4,2,3] => [.,[[[.,.],.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
[2,1,4,3,5] => [[.,.],[[.,.],[.,.]]]
=> ([(0,4),(1,4),(2,3),(3,4)],5)
=> 2 = 3 - 1
Description
The matching number of a graph. For a graph G, this is defined as the maximal size of a '''matching''' or '''independent edge set''' (a set of edges without common vertices) contained in G.
The following 138 statistics, ordered by result quality, also match your data. Click on any of them to see the details.
St000985The number of positive eigenvalues of the adjacency matrix of the graph. St001517The length of a longest pair of twins in a permutation. St001667The maximal size of a pair of weak twins for a permutation. St001794Half the number of sets of vertices in a graph which are dominating and non-blocking. St001812The biclique partition number of a graph. St000363The number of minimal vertex covers of a graph. St001108The 2-dynamic chromatic number of a graph. St001110The 3-dynamic chromatic number of a graph. St001315The dissociation number of a graph. St001674The number of vertices of the largest induced star graph in the graph. St001725The harmonious chromatic number of a graph. St000171The degree of the graph. St001117The game chromatic index of a graph. St001349The number of different graphs obtained from the given graph by removing an edge. St001572The minimal number of edges to remove to make a graph bipartite. St001573The minimal number of edges to remove to make a graph triangle-free. St001704The size of the largest multi-subset-intersection of the deck of a graph with the deck of another graph. St001118The acyclic chromatic index of a graph. St001629The coefficient of the integer composition in the quasisymmetric expansion of the relabelling action of the symmetric group on cycles. St000699The toughness times the least common multiple of 1,. St001060The distinguishing index of a graph. St001570The minimal number of edges to add to make a graph Hamiltonian. St001603The number of colourings of a polygon such that the multiplicities of a colour are given by a partition. St001604The multiplicity of the irreducible representation corresponding to a partition in the relabelling action on polygons. St000264The girth of a graph, which is not a tree. St001123The multiplicity of the dual of the standard representation in the Kronecker square corresponding to a partition. St001198The number of simple modules in the algebra eAe with projective dimension at most 1 in the corresponding Nakayama algebra A with minimal faithful projective-injective module eA. St001200The number of simple modules in eAe with projective dimension at most 2 in the corresponding Nakayama algebra A with minimal faithful projective-injective module eA. St001206The maximal dimension of an indecomposable projective eAe-module (that is the height of the corresponding Dyck path) of the corresponding Nakayama algebra with minimal faithful projective-injective module eA. St001199The dominant dimension of eAe for the corresponding Nakayama algebra A with minimal faithful projective-injective module eA. St000514The number of invariant simple graphs when acting with a permutation of given cycle type. St000515The number of invariant set partitions when acting with a permutation of given cycle type. St000284The Plancherel distribution on integer partitions. St000510The number of invariant oriented cycles when acting with a permutation of given cycle type. St000681The Grundy value of Chomp on Ferrers diagrams. St000698The number of 2-rim hooks removed from an integer partition to obtain its associated 2-core. St000704The number of semistandard tableaux on a given integer partition with minimal maximal entry. St000901The cube of the number of standard Young tableaux with shape given by the partition. St001128The exponens consonantiae of a partition. St000512The number of invariant subsets of size 3 when acting with a permutation of given cycle type. St000936The number of even values of the symmetric group character corresponding to the partition. St000938The number of zeros of the symmetric group character corresponding to the partition. St000940The number of characters of the symmetric group whose value on the partition is zero. St000941The number of characters of the symmetric group whose value on the partition is even. St001124The multiplicity of the standard representation in the Kronecker square corresponding to a partition. St001875The number of simple modules with projective dimension at most 1. St001605The number of colourings of a cycle such that the multiplicities of colours are given by a partition. St001630The global dimension of the incidence algebra of the lattice over the rational numbers. St001878The projective dimension of the simple modules corresponding to the minimum of L in the incidence algebra of the lattice L. St001876The number of 2-regular simple modules in the incidence algebra of the lattice. St001877Number of indecomposable injective modules with projective dimension 2. St001879The number of indecomposable summands of the top of the first syzygy of the dual of the regular module in the incidence algebra of the lattice. St000454The largest eigenvalue of a graph if it is integral. St001880The number of 2-Gorenstein indecomposable injective modules in the incidence algebra of the lattice. St001195The global dimension of the algebra A/AfA of the corresponding Nakayama algebra A with minimal left faithful projective-injective module Af. St001031The height of the bicoloured Motzkin path associated with the Dyck path. St000455The second largest eigenvalue of a graph if it is integral. St000259The diameter of a connected graph. St001624The breadth of a lattice. St000092The number of outer peaks of a permutation. St000099The number of valleys of a permutation, including the boundary. St000298The order dimension or Dushnik-Miller dimension of a poset. St000537The cutwidth of a graph. St000633The size of the automorphism group of a poset. St000640The rank of the largest boolean interval in a poset. St000778The metric dimension of a graph. St000813The number of zero-one matrices with weakly decreasing column sums and row sums given by the partition. St000846The maximal number of elements covering an element of a poset. St000903The number of different parts of an integer composition. St001235The global dimension of the corresponding Comp-Nakayama algebra. St001270The bandwidth of a graph. St001399The distinguishing number of a poset. St001503The largest distance of a vertex to a vertex in a cycle in the resolution quiver of the corresponding Nakayama algebra. St001621The number of atoms of a lattice. St001644The dimension of a graph. St001724The 2-packing differential of a graph. St001741The largest integer such that all patterns of this size are contained in the permutation. St001962The proper pathwidth of a graph. St000023The number of inner peaks of a permutation. St000353The number of inner valleys of a permutation. St000601The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal, (2,3) are consecutive in a block. St000638The number of up-down runs of a permutation. St000671The maximin edge-connectivity for choosing a subgraph. St000706The product of the factorials of the multiplicities of an integer partition. St000717The number of ordinal summands of a poset. St000872The number of very big descents of a permutation. St000927The alternating sum of the coefficients of the character polynomial of an integer partition. St000939The number of characters of the symmetric group whose value on the partition is positive. St000993The multiplicity of the largest part of an integer partition. St001022Number of simple modules with projective dimension 3 in the Nakayama algebra corresponding to the Dyck path. St001097The coefficient of the monomial symmetric function indexed by the partition in the formal group law for linear orders. St001098The coefficient times the product of the factorials of the parts of the monomial symmetric function indexed by the partition in the formal group law for vertex labelled trees. St001112The 3-weak dynamic number of a graph. St001174The Gorenstein dimension of the algebra A/I when I is the tilting module corresponding to the permutation in the Auslander algebra of K[x]/(x^n). St001181Number of indecomposable injective modules with grade at least 3 in the corresponding Nakayama algebra. St001353The number of prime nodes in the modular decomposition of a graph. St001568The smallest positive integer that does not appear twice in the partition. St001638The book thickness of a graph. St001642The Prague dimension of a graph. St001729The number of visible descents of a permutation. St001890The maximum magnitude of the Möbius function of a poset. St000567The sum of the products of all pairs of parts. St000620The number of standard tableaux of shape equal to the given partition such that the minimal cyclic descent is odd. St000668The least common multiple of the parts of the partition. St000707The product of the factorials of the parts. St000708The product of the parts of an integer partition. St000713The dimension of the irreducible representation of Sp(4) labelled by an integer partition. St000714The number of semistandard Young tableau of given shape, with entries at most 2. St000770The major index of an integer partition when read from bottom to top. St000815The number of semistandard Young tableaux of partition weight of given shape. St000929The constant term of the character polynomial of an integer partition. St000933The number of multipartitions of sizes given by an integer partition. St000937The number of positive values of the symmetric group character corresponding to the partition. St001099The coefficient times the product of the factorials of the parts of the monomial symmetric function indexed by the partition in the formal group law for leaf labelled binary trees. St001100The coefficient times the product of the factorials of the parts of the monomial symmetric function indexed by the partition in the formal group law for leaf labelled trees. St001101The coefficient times the product of the factorials of the parts of the monomial symmetric function indexed by the partition in the formal group law for increasing trees. St001746The coalition number of a graph. St000478Another weight of a partition according to Alladi. St000566The number of ways to select a row of a Ferrers shape and two cells in this row. St000621The number of standard tableaux of shape equal to the given partition such that the minimal cyclic descent is even. St000934The 2-degree of an integer partition. St000477The weight of a partition according to Alladi. St000509The diagonal index (content) of a partition. St000928The sum of the coefficients of the character polynomial of an integer partition. St000997The even-odd crank of an integer partition. St000716The dimension of the irreducible representation of Sp(6) labelled by an integer partition. St001805The maximal overlap of a cylindrical tableau associated with a semistandard tableau. St001926Sparre Andersen's position of the maximum of a signed permutation. St000990The first ascent of a permutation. St000570The Edelman-Greene number of a permutation. St000654The first descent of a permutation. St000873The aix statistic of a permutation. St001859The number of factors of the Stanley symmetric function associated with a permutation. St000102The charge of a semistandard tableau. St000279The size of the preimage of the map 'cycle-as-one-line notation' from Permutations to Permutations. St000516The number of stretching pairs of a permutation. St000623The number of occurrences of the pattern 52341 in a permutation. St000803The number of occurrences of the vincular pattern |132 in a permutation.