Seidel Minor, Permutation Graphs and Combinatorial Properties

Details Seidel Minor, Permutation Graphs and Combinatorial Properties Seidel Minor, Permutation Graphs and Combinatorial Properties

2009-04-13

arxiv.org/abs/0904.1923v2

Computer Science

Discrete Mathematics

submitted

Scientific paper

A permutation graph is an intersection graph of segments lying between two parallel lines. A Seidel complementation of a finite graph at one of it vertex $v$ consists to complement the edges between the neighborhood and the non-neighborhood of $v$. Two graphs are Seidel complement equivalent if one can be obtained from the other by a successive application of Seidel complementation. In this paper we introduce the new concept of Seidel complementation and Seidel minor, we then show that this operation preserves cographs and the structure of modular decomposition. The main contribution of this paper is to provide a new and succinct characterization of permutation graphs i.e. A graph is a permutation graph \Iff it does not contain the following graphs: $C_5$, $C_7$, $XF_{6}^{2}$, $XF_{5}^{2n+3}$, $C_{2n}, n\geqslant6$ and their complement as Seidel minor. In addition we provide a $O(n+m)$-time algorithm to output one of the forbidden Seidel minor if the graph is not a permutation graph.

Affiliated with

Also associated with

No associations

Rating

Seidel Minor, Permutation Graphs and Combinatorial Properties 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 Seidel Minor, Permutation Graphs and Combinatorial Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Seidel Minor, Permutation Graphs and Combinatorial Properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324098