GraphPackingNumber
The most vertices, no two within distance 2: the closed neighborhoods of the vertices are disjoint.
✓ checked against that system · ! checked, with disagreements (hover a chip)FindStat
St000916via LabeledGraph✓GraphPackingNumber(graph)The most vertices, no two within distance 2: the closed neighborhoods of the vertices are disjoint.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 St000916. A set is a packing when every vertex has at most one member among itself and 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 if m %
2 ^ w >=
2 ^
(w - 1) else 0) >
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 |