login
Number of n-node graphs with the maximum number (A352766(n)) of orientations.
1

%I #5 Apr 16 2022 05:48:49

%S 1,2,1,1,2,1,2,1,2,1,2,4,10

%N Number of n-node graphs with the maximum number (A352766(n)) of orientations.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FanGraph.html">Fan Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HouseGraph.html">House Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpiderGraph.html">Spider Graph</a>

%e For 1 <= n <= 13, the n-node graphs having A352766(n) orientations are listed below. Here, CU(G_1, ..., G_k) denotes the complement of the disjoint union of the graphs G_1, ..., G_k, P_m is the m-node path, and S(m_1, ..., m_k) denotes the spider graph with legs of lengths m_1, ..., m_k.

%e n = 1: P_1;

%e n = 2: P_2 and 2*P_1;

%e n = 3: P_3;

%e n = 4: CU(P_1, P_1, P_2) (the diamond graph);

%e n = 5: CU(P_1, P_4) (the fan graph F_{1,4}) and CU(P_1, P_1, P_3) (the house X-graph);

%e n = 6: CU(P_1, P_2, P_3);

%e n = 7: CU(P_1, P_2, P_4) and CU(P_1, P_1, P_2, P_3);

%e n = 8: CU(P_1, S(1, 2, 3));

%e n = 9: CU(P_1, P_1, S(1, 2, 3)) and CU(P_1, S(1, 2, 4));

%e n = 10: CU(P_1, P_2, S(1, 2, 3));

%e n = 11: CU(P_1, P_1, P_2, S(1, 2, 3)) and CU(P_1, P_2, S(1, 2, 4));

%e n = 12: CU(P_1, P_1, P_2, S(1, 2, 4)) and CU(P_1, P_2, T), where T is any of the three asymmetric trees on 9 nodes (S(1, 2, 5), S(1, 3, 4), or a 7-node path with two additional nodes joined to the 3rd and 4th node of the path, respectively);

%e n = 13: CU(P_1, P_2, P_3, S(1, 2, 3)), CU(P_1, P_1, P_2, T), where T is any of the three asymmetric trees on 9 nodes, and CU(P_1, P_2, T), where T is any of the six asymmetric trees on 10 nodes.

%Y Cf. A352766.

%K nonn,more

%O 1,2

%A _Pontus von Brömssen_, Apr 02 2022