Your data matches 32 different statistics following compositions of up to 3 maps.
(click to perform a complete search on your data)
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001330: 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)
=> ([(0,1)],2)
=> 2
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 2
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 3
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 2
Description
The hat guessing number of a graph. Suppose that each vertex of a graph corresponds to a player, wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The hat guessing number $HG(G)$ of a graph $G$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ possible colors. Because it suffices that a single player guesses correctly, the hat guessing number of a graph is the maximum of the hat guessing numbers of its connected components.
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001580: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 2
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 2
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 3
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 2
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
Description
The acyclic chromatic number of a graph. This is the smallest size of a vertex partition $\{V_1,\dots,V_k\}$ such that each $V_i$ is an independent set and for all $i,j$ the subgraph inducted by $V_i\cup V_j$ does not contain a cycle.
Matching statistic: St001883
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001883: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 2
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 2
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 2
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 2
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 3
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 2
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 2
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 2
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 2
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 2
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 2
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 2
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 2
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2
Description
The mutual visibility number of a graph. This is the largest cardinality of a subset $P$ of vertices of a graph $G$, such that for each pair of vertices in $P$ there is a shortest path in $G$ which contains no other point in $P$. In particular, the mutual visibility number of the disjoint union of two graphs is the maximum of their mutual visibility numbers.
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St000272: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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.
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St000536: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
Description
The pathwidth of a graph.
Matching statistic: St000537
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St000537: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001270: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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.
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001277: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001358: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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].
Mp00185: Skew partitions cell posetPosets
Mp00074: Posets to graphGraphs
St001644: Graphs ⟶ ℤResult quality: 96% values known / values provided: 96%distinct values known / distinct values provided: 100%
Values
[[1],[]]
=> ([],1)
=> ([],1)
=> 0 = 1 - 1
[[2],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[1,1],[]]
=> ([(0,1)],2)
=> ([(0,1)],2)
=> 1 = 2 - 1
[[2,1],[1]]
=> ([],2)
=> ([],2)
=> 0 = 1 - 1
[[3],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,1],[]]
=> ([(0,1),(0,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,2],[1]]
=> ([(0,2),(1,2)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[3,2],[2]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[1,1,1],[]]
=> ([(0,2),(2,1)],3)
=> ([(0,2),(1,2)],3)
=> 1 = 2 - 1
[[2,2,1],[1,1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[2,1,1],[1]]
=> ([(1,2)],3)
=> ([(1,2)],3)
=> 1 = 2 - 1
[[3,2,1],[2,1]]
=> ([],3)
=> ([],3)
=> 0 = 1 - 1
[[4],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2],[]]
=> ([(0,1),(0,2),(1,3),(2,3)],4)
=> ([(0,2),(0,3),(1,2),(1,3)],4)
=> 2 = 3 - 1
[[3,2],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,2],[2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[2,1,1],[]]
=> ([(0,2),(0,3),(3,1)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[1,1]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,1,1],[1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[4,2,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,3],[2]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[4,3],[3]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1],[1]]
=> ([(0,3),(1,2),(1,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,1],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,1],[2]]
=> ([(1,2),(1,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,1],[3,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,2,2],[1,1]]
=> ([(0,3),(1,2),(2,3)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[3,3,2],[2,2]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,2,2],[2,1]]
=> ([(1,3),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[4,3,2],[3,2]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[1,1,1,1],[]]
=> ([(0,3),(2,1),(3,2)],4)
=> ([(0,3),(1,2),(2,3)],4)
=> 1 = 2 - 1
[[2,2,2,1],[1,1,1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[2,2,1,1],[1,1]]
=> ([(0,3),(1,2)],4)
=> ([(0,3),(1,2)],4)
=> 1 = 2 - 1
[[3,3,2,1],[2,2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[2,1,1,1],[1]]
=> ([(1,2),(2,3)],4)
=> ([(1,3),(2,3)],4)
=> 1 = 2 - 1
[[3,2,2,1],[2,1,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[3,2,1,1],[2,1]]
=> ([(2,3)],4)
=> ([(2,3)],4)
=> 1 = 2 - 1
[[4,3,2,1],[3,2,1]]
=> ([],4)
=> ([],4)
=> 0 = 1 - 1
[[5],[]]
=> ([(0,4),(2,3),(3,1),(4,2)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,1],[]]
=> ([(0,2),(0,4),(3,1),(4,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,1],[1]]
=> ([(1,4),(3,2),(4,3)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,2],[1]]
=> ([(0,4),(1,2),(1,4),(2,3)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[5,2],[2]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[3,1,1],[]]
=> ([(0,3),(0,4),(3,2),(4,1)],5)
=> ([(0,4),(1,3),(2,3),(2,4)],5)
=> 1 = 2 - 1
[[4,2,1],[1,1]]
=> ([(1,3),(1,4),(4,2)],5)
=> ([(1,4),(2,3),(3,4)],5)
=> 1 = 2 - 1
[[4,1,1],[1]]
=> ([(0,3),(1,4),(4,2)],5)
=> ([(0,1),(2,4),(3,4)],5)
=> 1 = 2 - 1
[[5,2,1],[2,1]]
=> ([(2,3),(3,4)],5)
=> ([(2,4),(3,4)],5)
=> 1 = 2 - 1
[[8],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[7,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[6,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,4),(4,1),(5,2),(6,5),(7,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,1,1,1,1,1],[]]
=> ([(0,6),(0,7),(3,5),(4,3),(5,2),(6,4),(7,1)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,1,1,1,1,1,1],[]]
=> ([(0,2),(0,7),(3,4),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[1,1,1,1,1,1,1,1],[]]
=> ([(0,7),(2,4),(3,2),(4,6),(5,3),(6,1),(7,5)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,1,1,1,1],[1,1]]
=> ([(0,3),(1,6),(1,7),(3,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,2,1,1,1,1],[1]]
=> ([(0,6),(0,7),(1,3),(1,7),(4,5),(5,2),(6,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[2,2,2,2,2,1,1],[1,1,1,1]]
=> ([(0,5),(1,6),(1,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[3,3,3,3,3,2],[2,2,2,2,1]]
=> ([(0,3),(1,6),(2,6),(2,7),(3,5),(4,7),(5,4)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,3,3,2],[3,2,2,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,4,2],[4,3,1]]
=> ([(0,5),(1,6),(2,5),(2,7),(3,4),(3,6),(4,7)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,3,3,3],[2,2,2]]
=> ([(0,4),(1,5),(1,6),(3,7),(4,7),(5,2),(6,3)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[4,4,4,4,4],[3,3,3,3]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 1
[[5,5,5,5],[4,4,4]]
=> ([(0,5),(1,6),(2,7),(3,7),(4,3),(5,4),(6,2)],8)
=> ([(0,7),(1,6),(2,3),(2,4),(3,5),(4,6),(5,7)],8)
=> ? = 2 - 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.
The following 22 statistics, ordered by result quality, also match your data. Click on any of them to see the details.
St001792The arboricity of a graph. St001962The proper pathwidth of a graph. St001592The maximal number of simple paths between any two different vertices of a graph. St000640The rank of the largest boolean interval in a poset. St000822The Hadwiger number of the graph. St001642The Prague dimension of a graph. St001331The size of the minimal feedback vertex set. St000455The second largest eigenvalue of a graph if it is integral. St000781The number of proper colouring schemes of a Ferrers diagram. St001901The largest multiplicity of an irreducible representation contained in the higher Lie character for an integer partition. St001934The number of monotone factorisations of genus zero of a permutation of given cycle type. St000205Number of non-integral Gelfand-Tsetlin polytopes with prescribed top row and partition weight. St000206Number of non-integral Gelfand-Tsetlin polytopes with prescribed top row and integer composition weight. St001175The size of a partition minus the hook length of the base cell. St000264The girth of a graph, which is not a tree. 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. St001875The number of simple modules with projective dimension at most 1. St001877Number of indecomposable injective modules with projective dimension 2. St001060The distinguishing index of a graph. St000456The monochromatic index of a connected graph. St000454The largest eigenvalue of a graph if it is integral.