Multiple Petersen subdivisions in permutation graphs

Details Multiple Petersen subdivisions in permutation graphs Multiple Petersen subdivisions in permutation graphs

2012-04-09

arxiv.org/abs/1204.1989v1

Mathematics

Combinatorics

Scientific paper

A permutation graph is a cubic graph admitting a 1-factor M whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if e is an edge of M such that every 4-cycle containing an edge of M contains e, then e is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5-edge-connected, then every edge of M is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.

Affiliated with

Also associated with

No associations

Rating

Multiple Petersen subdivisions in permutation graphs 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 Multiple Petersen subdivisions in permutation graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple Petersen subdivisions in permutation graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643697