A323658 Number of bipartite graphs associated with connected transitive oriented graphs.

1, 1, 1, 2, 7, 25, 133, 854

Offset: 0

Author

M. Farrokhi D. G., Jan 23 2019

Keywords

• nonn
• hard
• more

Comments

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

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.

Examples

			Example: For n = 4 the a(4) = 7 solutions are given by the edge sets
E1 = {(1,5), (1,7), (2,6), (2,7), (2,8), (3,7), (4,8)},
E2 = {(1,5), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E3 = {(1,5), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E4 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (4,8)},
E5 = {(1,5), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)},
E6 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,8), (3,7), (3,8), (4,8)},
E7 = {(1,5), (1,6), (1,7), (1,8), (2,6), (2,7), (2,8), (3,7), (3,8), (4,8)}.
		

Links

• M. Estrada and R. H. Villarreal, Cohen-Macaulay bipartite graphs, Arch. Math. (Basel) 68(2) (1997), 124-128.
• J. Herzog and T. Hibi, Distributive lattices, bipartite graphs and Alexander duality, J. Algebraic Combin. 22(3) (2005), 289-302.
• M. Mahmoudi and A. Mousivand, An alternative proof of a characterization of Cohen-Macaulay bipartite graphs, Abh. Math. Semin. Univ. Hambg. 80(1) (2010), 145-148.
• R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66(3) (1990), 277-293.
• R. H. Villarreal, Unmixed bipartite graphs, Rev. Colomb. Mat. 41(2) (2007), 393-395.
• R. Zaare-Nahandi, Cohen-Macaulayness of bipartite graphs, revisited, Bull. Malays. Math. Sci. Soc. 38(4) (2015), 1601-1607.

Crossrefs

Cf. A006455, A323502.