The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems

Details The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems

2009-09-22

arxiv.org/abs/0909.4004v4

Computer Science

Discrete Mathematics

21 pages, 7 figures, significant additions w.r.t. v3 are Thm 7 and Remark 25

Scientific paper

We study the interplay between principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S_3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized.

Affiliated with

Also associated with

No associations

Rating

The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems 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 Group Structure of Pivot and Loop Complementation on Graphs and Set Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-301008