A382759 -id:A382759 - cp's OEIS frontend

A382754 List of unlabeled simple graphs, encoded as integers (see comments).

0, 1, 2, 3, 8, 9, 11, 15, 64, 65, 67, 71, 75, 76, 77, 79, 94, 95, 127, 1024, 1025, 1027, 1031, 1039, 1043, 1044, 1045, 1047, 1052, 1053, 1055, 1078, 1079, 1082, 1083, 1086, 1087, 1150, 1151, 1207, 1208, 1209, 1211, 1215, 1231, 1244, 1245, 1247, 1278, 1279, 1519, 1535, 2047

Offset: 0

Pontus von Brömssen, Apr 04 2025

For a graph G, pick a permutation of its vertices that minimizes the bitstring obtained by reading the lower triangular part of the corresponding adjacency matrix by rows. The code of G is that bitstring interpreted as a binary number plus 2^(v*(v-1)/2), where v is the number of vertices of G; see example. As a special case, the code of the null graph is 0. The sequence consists of all such minimal codes.
For n >= 1, the numbers of vertices and edges of the graph with code a(n) are A002024(A000523(a(n))+1) and A000120(a(n))-1 = A382758(n), respectively.
This sequence can be used to define sequences for:
  - graph invariants (examples: A382758, A382759, A382760);
  - graph operators, either by code (A382763) or by index (A382764);
  - lists of subsets of graphs, either by code (A382761) or by index (A382762).

			As an irregular triangle, where row n >= 0 contains A000088(n) terms:
   0;
   1;
   2,  3;
   8,  9, 11, 15;
  64, 65, 67, 71, 75, 76, 77, 79, 94, 95, 127;
  ...
71 is a term, because it is the code of the claw graph. If the edges are taken to be (0,1), (0,2), and (0,3), an optimal permutation of the vertices of the graph is (3, 2, 1, 0), with the lower triangular part of the corresponding adjacency matrix being [0; 0,0; 1,1,1]. Adding 2^(4*3/2) to the binary number 000111, we obtain that the code of the claw graph is 64+7 = 71.

Pontus von Brömssen, Table of n, a(n) for n = 0..13598 (for graphs on up to 8 vertices)

Cf. A000088, A000120, A000523, A002024, A076184, A382755, A382756, A382757, A382758, A382759, A382760, A382761, A382762, A382763, A382764.

cp's OEIS Frontend

A382754 List of unlabeled simple graphs, encoded as integers (see comments).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs