GraphOpenPackingNumber
The most vertices with pairwise disjoint sets of neighbors.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St000917via LabeledGraph✓GraphOpenPackingNumber(graph)The most vertices with pairwise disjoint sets of neighbors.Typed signatures
| Type | Package | Applies |
|---|---|---|
(labeled_graph) -> number | combinatorics | always |
Details
- Defined over
LabeledGraphas an expression in_x, evaluated by compute-engine — the definition IS the implementation. - Takes a
LabeledGraphand nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer. - FindStat's St000917. A set is an open packing when every vertex has at most one member among its neighbors. The graph with no vertices gives 0.
Definition
Epsil, as the implementation runs it.
on LabeledGraph, over _x
0 if _x[1] == 0 else Apply((n: integer) => Apply((edges: list<list<integer>>) => Apply(
(inside: list<integer>) => Apply(
(totals: list<integer>) => Apply(
(toSet: list<list<integer>>) => Max(Map(Function((1 if Max(Sum(Map(Function(1 if toSet[m + 1][w] >
1 else 0, w), Range(1, n))), 0) ==
0 else 0) *
totals[m + 1], m), Range(0, 2 ^ n -
1))),
Map(
Function(Map(Function(Max(Sum(Map(Function((1 if e[1] == v else 0) *
(1 if m %
2 ^ e[2] >=
2 ^
(e[2] - 1) else 0) +
(1 if e[2] == v else 0) *
(1 if m %
2 ^ e[1] >=
2 ^
(e[1] - 1) else 0), e), edges)), 0), v), Range(1, n)), m),
Range(0, 2 ^ n -
1),
),
),
Map(
Function(Max(Sum(Map(Function(1 if m %
2 ^ v >=
2 ^
(v - 1) else 0, v), Range(1, n))), 0), m),
Range(0, 2 ^ n -
1),
),
),
Map(
Function(Max(Sum(Map(Function((1 if m %
2 ^ e[1] >=
2 ^
(e[1] - 1) else 0) *
(1 if m %
2 ^ e[2] >=
2 ^
(e[2] - 1) else 0), e), edges)), 0), m),
Range(0, 2 ^ n -
1),
),
), _x[2]), _x[1])Examples
Properties #
About
| Examples | 4 |
|---|---|
| Crosswalk | FindStat |