LabeledGraphsByEdges
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Graphs on [n] with exactly m edges — the (n,m) refinement of labeled_graphs.
LabeledGraphsByEdges(...)Graphs on [n] with exactly m edges — the (n,m) refinement of labeled_graphs.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>, integer<0..>) -> indexed_collection<labeled_graph> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n, _m)
Binomial(Binomial(_n, 2) if 0 <= 2 && 2 <= _n else 0, _m) if 0 <= _m && _m <=
(Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) else 0unrank(_n, _m, _r)
Apply(
(bd: list<integer>) => Map(Function(Apply(
(bu_k: integer) => Apply((bu_u: integer) => Apply(
(bu_v: integer) => [bu_u, bu_v],
bu_k -
((Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) -
(Binomial(_n - bu_u +
1, 2) if 0 <= 2 &&
2 <=
_n - bu_u +
1 else 0)) +
bu_u,
), _tables[bu_k]),
bd[bi + 1] + 1,
), bi), Range(1, _m, 1)),
Apply(
(bd_st_init: list<integer>) => Fold((bd_st: list<integer>, bd_i) => Apply(
(bd_st_next: list<integer>) => bd_st_next,
Apply((bd_left: integer) => Apply(
(bd_found: integer) => ReplaceAt(ReplaceAt(bd_st, 1, bd_left -
_tables[(Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) +
bd_found *
(Max(0, Min(_m, Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0)) +
1) +
bd_i +
1]), bd_i + 1, bd_found),
Fold(
Function(bd_c if _tables[(Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) +
bd_c *
(Max(0, Min(_m, Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0)) +
1) +
bd_i +
1] <=
bd_left else bd_best, bd_best, bd_c),
bd_i - 1,
Range(
bd_i - 1,
((Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) if bd_i == _m else bd_st[bd_i + 2]) -
1,
1,
),
),
), bd_st[1]),
), bd_st_init, Range(_m, 1, -1)),
Join([_r], Map(Function(0, bd_z), Range(1, _m, 1))),
),
)rank(_n, _m, _x)
Apply(
(bx: list<integer>) => Fold(Function(br + _tables[(Binomial(_n, 2) if 0 <=
2 &&
2 <=
_n else 0) +
(bx[bi] - 1) *
(Max(
0,
Min(
_m,
Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0,
),
) + 1) + bi + 1], br, bi), 0, Range(1, Length(_x), 1)),
Sort(Map(Function((Binomial(_n, 2) if 0 <= 2 && 2 <= _n else 0) -
(Binomial(_n - Min(_x[bj][1], _x[bj][2]) + 1, 2) if 0 <=
2 &&
2 <=
_n -
Min(_x[bj][1], _x[bj][2]) +
1 else 0) + (Max(_x[bj][1], _x[bj][2]) - Min(
_x[bj][1],
_x[bj][2],
)), bj), Range(
1,
Length(_x),
1,
))),
)valid(_n, _m, _x)
Fold(Function(ok_wb && 1 <= _x[wb][1] && _x[wb][1] <= _n && 1 <= _x[wb][2] &&
_x[wb][2] <= _n && _x[wb][1] != _x[wb][2], ok_wb, wb), True, Range(1, Length(_x), 1)) && Fold(
Function(ok_wj &&
Fold(
Function(ok_wi &&
(Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) -
(Binomial(_n -
Min(_x[wi][1], _x[wi][2]) +
1, 2) if 0 <= 2 &&
2 <=
_n -
Min(_x[wi][1], _x[wi][2]) +
1 else 0) +
(Max(_x[wi][1], _x[wi][2]) -
Min(_x[wi][1], _x[wi][2])) !=
(Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0) -
(Binomial(_n -
Min(_x[wj][1], _x[wj][2]) +
1, 2) if 0 <= 2 &&
2 <=
_n -
Min(_x[wj][1], _x[wj][2]) +
1 else 0) +
(Max(_x[wj][1], _x[wj][2]) -
Min(_x[wj][1], _x[wj][2])), ok_wi, wi),
True,
Range(1, wj - 1, 1),
), ok_wj, wj),
True,
Range(1, Length(_x), 1),
) if Length(_x) ==
_m &&
Fold(
Function(ok_wp &&
Length(_x[wp]) == 2, ok_wp, wp),
True,
Range(1, Length(_x), 1),
) else Falsetables(_n, _m)
Join(
Fold(Function(
Join(et, Map(Function(eu, ez), Range(1, _n - eu, 1))),
et,
eu,
), [], Range(1, _n - 1, 1)),
Fold(
Function(Join(
bp_t,
Fold(
Function(ReplaceAt(
bp_row,
bp_c + 1,
1 if bp_c == 0 else bp_t[(bp_s -
1) *
(Max(
0,
Min(_m, Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0),
) +
1) +
(bp_c -
1) +
1] +
bp_t[(bp_s -
1) *
(Max(
0,
Min(_m, Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0),
) +
1) +
bp_c +
1],
), bp_row, bp_c),
Map(
Function(0, bp_z),
Range(
0,
Max(
0,
Min(
_m,
Binomial(_n, 2) if 0 <= 2 &&
2 <=
_n else 0,
),
) + 1 - 1,
1,
),
),
Range(0, Max(
0,
Min(
_m,
Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0,
),
) + 1 - 1, 1),
),
), bp_t, bp_s),
Fold(Function(
ReplaceAt(bp_row, bp_c + 1, 1 if bp_c == 0 else 0),
bp_row,
bp_c,
), Map(
Function(0, bp_z),
Range(0, Max(
0,
Min(
_m,
Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0,
),
) + 1 - 1, 1),
), Range(0, Max(
0,
Min(
_m,
Binomial(_n, 2) if 0 <= 2 &&
2 <= _n else 0,
),
) + 1 - 1, 1)),
Range(1, Max(Binomial(_n, 2) if 0 <= 2 && 2 <= _n else 0, 1) - 1, 1),
),
)Statistics
On LabeledGraph, called as CombinatorialStat(x, "Name").
- AboveAverageDegreeVertexCountSt001692The vertices whose degree is greater than the average degree.
- AbsoluteAdjacencyDeterminantSt001702The absolute value of the determinant of the adjacency matrix.
- AdjacencyDeterminantSt000351The determinant of the adjacency matrix.
- AlbertsonIndexSt001351The sum over the edges of the difference of the degrees of its ends.
- AnnihilationNumberSt001286The most vertices whose degrees add up to at most the number of edges.
- BipartiteEdgeDeletionNumberSt001572The fewest edges whose deletion leaves a bipartite graph.
- BlockCountSt000553The blocks: the maximal connected subgraphs with no cut vertex; an isolated vertex is a block.
- BridgeCountSt001479The edges whose deletion leaves more components.
- CelebrityCountSt001689The vertices of whom more than half the neighbors have a smaller degree.
- CenterEdgeCountSt001341The edges with both ends in the center.
- CenterVertexCountSt001342The vertices whose greatest distance to another vertex is the least.
- ChromaticCliqueGapSt001793The chromatic number less the clique number.
- ChromaticNumberSt000098The fewest colors for the vertices so that adjacent vertices differ.
- CliqueCocliqueNumberSt000926The clique number times the independence number.
- CliqueNumberSt000097The most vertices that are pairwise adjacent.
- ComplementComponentCountSt000286The connected components of the complement graph.
- ConnectedInducedSubgraphCountSt001441The nonempty sets of vertices that induce a connected subgraph.
- CutVertexCountSt000552The vertices whose deletion leaves more components.
- CyclomaticNumberSt001311The edges less the vertices plus the components: the independent cycles.
- DegeneracySt001277The greatest, over the sets of vertices, of the least number of neighbors a vertex has inside the set.
- DegreeRangeSt001742The greatest degree less the least.
- DegreeSumSt000350The sum of the degrees: twice the number of edges.
- DegreeTwoVertexCountSt000313The vertices with exactly two edges.
- DifferentDegreePairCountSt001708The pairs of vertices whose degrees differ.
- DissociationNumberSt001315The most vertices in a set in which every vertex has at most one neighbor.
- DistanceFourPairCountSt000449The pairs of vertices at distance 4.
- DistanceThreePairCountSt000447The pairs of vertices at distance 3.
- DistanceTwoPairCountSt000448The pairs of vertices at distance 2.
- DistinctNeighborhoodCountSt000722The different sets of neighbors the vertices have.
- DominatingSetCountSt001303The sets of vertices such that every vertex is in the set or adjacent to one of it.
- DominationNumberSt000273The fewest vertices such that every vertex is one of them or adjacent to one.
- EulerFaceCountSt000450The edges less the vertices plus 2: the faces of a connected planar graph.
- EvenDegreeVertexCountSt000309The vertices with an even number of edges.
- FeedbackVertexSetNumberSt001331The fewest vertices whose deletion leaves a graph with no cycle.
- FirstZagrebIndexSt000465The sum of the squares of the degrees.
- ForgottenIndexSt000571The sum of the cubes of the degrees.
- FourCliqueCountSt001309The sets of four vertices that are pairwise adjacent.
- GirthSt000264The length of the shortest cycle.
- GraphComponentCountSt000287The connected components: the vertices that are the first of their component.
- GraphCycleCountSt001736The cycles, each counted once however it is started or turned.
- GraphDifferentialSt001723The most that the vertices next to a set, outside it, exceed the set in number.
- GraphEdgeConnectivitySt000261The fewest edges whose deletion leaves a disconnected graph: the fewest edges between a set of vertices and the rest.
- GraphEdgeCountSt000081The edges of the graph.
- GraphLeafCountSt000312The vertices with exactly one edge.
- GraphLongestCycleLengthSt000637The length of the longest cycle.
- GraphOpenPackingNumberSt000917The most vertices with pairwise disjoint sets of neighbors.
- GraphPackingNumberSt000916The most vertices, no two within distance 2: the closed neighborhoods of the vertices are disjoint.
- GraphTwoLimitedPackingNumberSt000918The most vertices in a set that has at most two members among the closed neighborhood of any vertex.
- GraphVertexConnectivitySt000262The fewest vertices whose deletion leaves a disconnected graph; the complete graph on n vertices gives n - 1.
- GutmanIndexSt000466The sum over the pairs of vertices of the product of their degrees times their distance.
- HalfAlbertsonIndexSt001350Half the sum over the edges of the difference of the degrees of its ends.
- HalfTotalIrregularitySt001521Half the sum over the unordered pairs of vertices of the difference of their degrees.
- HosoyaIndexSt000468The sets of edges with no two sharing a vertex, the empty set included.
- HyperWienerIndexSt000467The sum over the pairs of vertices of their distance plus its square.
- IndependenceGapSt001323The independence number less the fewest vertices of a maximal independent set.
- IndependenceNumberSt000093The most vertices that are pairwise non-adjacent.
- IndependentDominationNumberSt001322The fewest vertices in a set that is independent and dominating: a maximal independent set.
- IndependentSetCountSt000300The sets of vertices, the empty set included, with no two adjacent.
- InducedDiamondCountSt001310The sets of four vertices that induce a diamond: a cycle on four vertices with one chord, five edges.
- InducedFourCycleCountSt001305The sets of four vertices that induce a cycle: every one has exactly two neighbors among the four.
- InducedMatchingNumberSt001393The most edges whose ends induce a subgraph that is just those edges.
- InducedPathOnFourVerticesCountSt001306The sets of four vertices that induce a path: three edges, and every vertex has one or two neighbors among the four.
- InducedPathOnThreeVerticesCountSt001308The sets of three vertices that induce a path: exactly two of the three edges.
- InducedStarOnFourVerticesCountSt001307The sets of four vertices that induce a star: three edges, and one vertex has all three others as neighbors.
- IsolatedVertexCountSt000315The vertices with no edge.
- KingCountSt001691The vertices whose neighbors all have a smaller degree; an isolated vertex counts.
- LargestInducedForestSizeSt001321The most vertices that induce a graph with no cycle.
- LargestInducedStarSizeSt001674The most vertices that induce a star: one vertex adjacent to all the others, which are not adjacent to each other. A single vertex is a star.
- LongestPathLengthSt001120The edges of the longest path.
- MatchingNumberSt000387The most edges with no two sharing a vertex.
- MaximalIndependentSetCountSt001304The independent sets of vertices that no vertex can be added to.
- MaximumCutSizeSt001869The most edges between the two sides of a division of the vertices.
- MaximumDegreeSt000171The greatest number of edges at one vertex.
- MaximumDegreeMultiplicitySt001366The most vertices that share one degree.
- MaximumDegreeVertexCountSt001368The vertices whose degree is the greatest.
- MaximumDistanceSt000259The greatest distance between two vertices: the diameter.
- MaximumLeafNeighborCountSt001826The most neighbors of degree 1 a vertex has.
- MaximumNeighborhoodMultiplicitySt000723The most vertices that have the same set of neighbors.
- MinimalDominatingSetCountSt001302The dominating sets that stop dominating when any vertex is dropped.
- MinimumDegreeSt000310The fewest edges at one vertex.
- MinimumEccentricitySt000260The least eccentricity of a vertex, the greatest distance from it to another vertex: the radius.
- MinimumVertexCoverCountSt000363The vertex covers with the fewest vertices: the independent sets with the most.
- NonTriangleVertexCountSt001996The vertices on no triangle.
- OddDegreeVertexCountSt000311The vertices with an odd number of edges.
- OreDegreeSt000915The greatest sum of the degrees of the two ends of an edge.
- PerfectMatchingCountSt000274The sets of edges that meet every vertex exactly once.
- SameNeighborhoodPairCountSt001347The pairs of vertices that have the same set of neighbors.
- SchultzIndexSt000464The sum over the pairs of vertices of the sum of their degrees times their distance.
- SecondZagrebIndexSt000361The sum over the edges of the product of the degrees of its ends.
- SmallestMissingDegreeSt001367The least number, 0 or more, that is not the degree of any vertex.
- SpanningSubgraphCountSt000343The subgraphs on all the vertices: 2 to the power of the number of edges.
- SpanningTreeCountSt000096The spanning trees: by the matrix-tree theorem, the determinant of the Laplacian with its last row and column deleted.
- SzegedIndexSt000263The sum over the edges of the vertices nearer one end times those nearer the other.
- TotalIrregularitySt001522The sum over the unordered pairs of vertices of the difference of their degrees.
- TriangleCountSt000095The triples of vertices that are pairwise adjacent.
- TriangleVertexCountSt001995The vertices on a triangle.
- TuranEdgeExcessSt001798The edges less those of the complement of the Turán graph with as many parts as the independence number: disjoint cliques as equal in size as possible.
- UpperDominationNumberSt001337The most vertices in a minimal dominating set.
- VertexCoverNumberSt000362The fewest vertices that meet every edge: the vertices less the independence number.
- WienerIndexSt000265The sum of the distances over the pairs of vertices that are joined by a path.
Maps
Into and out of LabeledGraph, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
28 more in FindStat, not implemented here
- Mp00011BinaryTree → LabeledGraphGraded mapto graph
- Mp00037LabeledGraph → IntegerPartitionSurjectionGraded mapto partition of connected components
- Mp00046OrderedTree → LabeledGraphGraded mapto graph
- Mp00074Posets → LabeledGraphGraded mapto graph
- Mp00111LabeledGraph → LabeledGraphBijectionGraded mapInvolutioncomplement
- Mp00117LabeledGraph → LabeledGraphIdempotentGraded mapOre closure
- Mp00147LabeledGraph → LabeledGraphGraded mapsquare
- Mp00152LabeledGraph → IntegerCompositionSurjectionGraded mapLaplacian multiplicities
- Mp00154LabeledGraph → LabeledGraphIdempotentcore
- Mp00156LabeledGraph → LabeledGraphline graph
- Mp00157LabeledGraph → LabeledGraphGraded mapInvolutionconnected complement
- Mp00160Permutation → LabeledGraphGraded mapgraph of inversions
- Mp00184IntegerComposition → LabeledGraphInjectionGraded mapto threshold graph
- Mp00198Posets → LabeledGraphGraded mapincomparability graph
- Mp00203LabeledGraph → LabeledGraphInjectionGraded mapcone
- Mp00243LabeledGraph → Posetsweak duplicate order
- Mp00247LabeledGraph → LabeledGraphIdempotentde-duplicate
- Mp00250LabeledGraph → LabeledGraphclique graph
- Mp00251LabeledGraph → IntegerPartitionclique sizes
- Mp00259LabeledGraph → LabeledGraphInjectionGraded mapvertex addition
- Mp00264LabeledGraph → LabeledGraphIdempotentdelete endpoints
- Mp00266LabeledGraph → Latticesconnected vertex partitions
- Mp00274LabeledGraph → LabeledGraphblock-cut tree
- Mp00275LabeledGraph → IntegerPartitionSurjectionto edge-partition of connected components
- Mp00276LabeledGraph → IntegerPartitionto edge-partition of biconnected components
- Mp00318LabeledGraph → LabeledGraphInvolutiondual on components
- Mp00324LabeledGraph → IntegerCompositionGraded mapchromatic difference sequence
- Mp00335Lattices → LabeledGraphzero-divisor graph