The Homomorphism Poset of K_{2,n}

Details The Homomorphism Poset of K_{2,n} The Homomorphism Poset of K_{2,n}

2010-08-10

arxiv.org/abs/1008.1736v2

Mathematics

Combinatorics

31 pages, 16 figures; added connections to permutation graphs; added a new section 4; new co-author

Scientific paper

A geometric graph is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. Two geometric realizations of a simple graph are geo-isomorphic if there is a vertex bijection between them that preserves vertex adjacencies and non-adjacencies, as well as edge crossings and non-crossings. A natural extension of graph homomorphisms, geo-homomorphisms, can be used to define a partial order on the set of geo-isomorphism classes of realizations of a given simple graph. In this paper, the homomorphism poset of the complete bipartite graph K_{2,n} is determined by establishing a correspondence between realizations of K_{2,n} and permutations of S_n, in which crossing edges correspond to inversions. Through this correspondence, geo-isomorphism defines an equivalence relation on S_n, which we call geo-equivalence. The number of geo-isomorphism classes is provided for all n <= 9. The modular decomposition tree of permutation graphs is used to prove some results on the size of geo-equivalence classes. A complete list of geo-equivalence classes and a Hasse diagrams of the poset structure are given for n <= 5.

Affiliated with

Also associated with

No associations

Rating

The Homomorphism Poset of K_{2,n} does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Homomorphism Poset of K_{2,n}, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Homomorphism Poset of K_{2,n} will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583994