cp's OEIS Frontend

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

%I A382754 #7 Apr 06 2025 15:03:43
%S A382754 0,1,2,3,8,9,11,15,64,65,67,71,75,76,77,79,94,95,127,1024,1025,1027,
%T A382754 1031,1039,1043,1044,1045,1047,1052,1053,1055,1078,1079,1082,1083,
%U A382754 1086,1087,1150,1151,1207,1208,1209,1211,1215,1231,1244,1245,1247,1278,1279,1519,1535,2047
%N A382754 List of unlabeled simple graphs, encoded as integers (see comments).
%C A382754 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.
%C A382754 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.
%C A382754 This sequence can be used to define sequences for:
%C A382754   - graph invariants (examples: A382758, A382759, A382760);
%C A382754   - graph operators, either by code (A382763) or by index (A382764);
%C A382754   - lists of subsets of graphs, either by code (A382761) or by index (A382762).
%H A382754 Pontus von Brömssen, <a href="/A382754/b382754.txt">Table of n, a(n) for n = 0..13598</a> (for graphs on up to 8 vertices)
%e A382754 As an irregular triangle, where row n >= 0 contains A000088(n) terms:
%e A382754    0;
%e A382754    1;
%e A382754    2,  3;
%e A382754    8,  9, 11, 15;
%e A382754   64, 65, 67, 71, 75, 76, 77, 79, 94, 95, 127;
%e A382754   ...
%e A382754 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.
%Y A382754 Cf. A000088, A000120, A000523, A002024, A076184, A382755, A382756, A382757, A382758, A382759, A382760, A382761, A382762, A382763, A382764.
%K A382754 nonn,tabf
%O A382754 0,3
%A A382754 _Pontus von Brömssen_, Apr 04 2025