A351335 Number of unlabeled directed graphs on n nodes without a subgraph isomorphic to directed K_{2,2} that have the maximal number of edges (=A191873(n)).

1, 1, 1, 1, 6, 5, 4, 829, 707, 2938, 55779, 60084

Offset: 1

Author

Max Alekseyev, Feb 07 2022

Keywords

• nonn
• more

Comments

When adjacency matrices viewed as those of bipartite graphs, these bipartite graphs are pairwise isomorphic for each n <= 12, except for n = 5 and n = 8 with 2 and 3 distinct bipartite graphs, respectively.

Examples

			For n = 7 there are 4 such graphs with A191873(7) = 21 edges, described by the following adjacency matrices:
[0111000]   [0110100]   [0110010]   [0010101]
[1010100]   [1011000]   [1000011]   [1001001]
[1100010]   [1000101]   [0101001]   [0100011]
[0100101]   [1100010]   [1100100]   [1010010]
[0010011]   [0010011]   [1011000]   [0111000]
[1001001]   [0101001]   [0010101]   [1100100]
[0001110]   [0001110]   [0001110]   [0001110]
Absence of directed K_{2,2} subgraph means that these matrices do not contain a rectangle with four 1s at the corners.
		

Crossrefs

Unlabeled version of A191874.

Directed version of A335820.

Cf. A191873.