A323658 - OEIS

%I #15 Jul 23 2019 08:53:38

%S 1,1,1,2,7,25,133,854

%N Number of bipartite graphs associated with connected transitive oriented graphs.

%C Also the number of unlabeled connected Cohen-Macaulay bipartite graphs up to graph isomorphism.

%C If G is an oriented graph with vertex set {1,...,n}, then the associated bipartite graph is a bipartite graph B(G) with parts {a1,...,an} and {b1,...,bn} such that ai ~ bj if (i,j) is an edge in G.

%H M. Estrada and R. H. Villarreal, <a href="https://doi.org/10.1007/s000130050040">Cohen-Macaulay bipartite graphs</a>, Arch. Math. (Basel) 68(2) (1997), 124-128.

%H J. Herzog and T. Hibi, <a href="https://doi.org/10.1007/s10801-005-4528-1">Distributive lattices, bipartite graphs and Alexander duality</a>, J. Algebraic Combin. 22(3) (2005), 289-302.

%H M. Mahmoudi and A. Mousivand, <a href="https://doi.org/10.1007/s12188-009-0032-1">An alternative proof of a characterization of Cohen-Macaulay bipartite graphs</a>, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.

%H R. H. Villarreal, <a href="https://doi.org/10.1007/BF02568497">Cohen-Macaulay graphs</a>, Manuscripta Math. 66(3) (1990), 277-293.

%H R. H. Villarreal, <a href="http://www.scielo.org.co/scielo.php?script=sci_arttext&amp;pid=S0034-74262007000200009">Unmixed bipartite graphs</a>, Rev. Colomb. Mat. 41(2) (2007), 393-395.

%H R. Zaare-Nahandi, <a href="https://doi.org/10.1007/s40840-014-0100-2">Cohen-Macaulayness of bipartite graphs, revisited</a>, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.

%e Example: For n = 4 the a(4) = 7 solutions are given by the edge sets

%e E1 = {(1,5), (1,7), (2,6), (2,7), (2,8), (3,7), (4,8)},

%e E2 = {(1,5), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},

%e E3 = {(1,5), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},

%e E4 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (4,8)},

%e E5 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},

%e E6 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},

%e E7 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)}.

%Y Cf. A006455, A323502.

%K nonn,hard,more

%O 0,4

%A _M. Farrokhi D. G._, Jan 23 2019