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

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

Offset

0,4

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.

Links

Table of n, a(n) for n=0..7.

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.

Example

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)}.

Crossrefs

Cf. A006455, A323502.

Sequence in context: A103464 A358498 A339515 * A018980 A012990 A137102

Adjacent sequences: A323655 A323656 A323657 * A323659 A323660 A323661

Keyword

nonn,hard,more

Author

M. Farrokhi D. G., Jan 23 2019

Status

approved