FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Research
a graph from permutations
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
Simone Severini
science forum beginner


Joined: 13 Mar 2005
Posts: 16

PostPosted: Fri May 19, 2006 11:45 am    Post subject: a graph from permutations Reply with quote
define a graph G_n as follows:

V(G_n) is the set of all permutations of length n;

vertices p_i and p_j are connected if the hamming distance between the
permutations p_i and p_j is exactly n.

e.g., G_3 is the disjoint union of two triangles.

what is G_n?

thanks,
simone severini
Back to top
Victor S. Miller
science forum beginner


Joined: 21 Jun 2005
Posts: 13

PostPosted: Tue May 23, 2006 1:30 pm    Post subject: Re: a graph from permutations Reply with quote
Quote:
"Simone" == ss54 <ss54@york.ac.uk> writes:

Simone> define a graph G_n as follows:

Simone> V(G_n) is the set of all permutations of length n;

Simone> vertices p_i and p_j are connected if the hamming distance
Simone> between the permutations p_i and p_j is exactly n.

Simone> e.g., G_3 is the disjoint union of two triangles.

Simone> what is G_n?

You might look at the paper "Hamilton-Connected Derangement Graphs on
Sn" (1994), by David J. Rasmussen and Carla D. Savage,

http://citeseer.ist.psu.edu/249672.html

In the paper, they study such graphs, and show that every pair of
vertices is joined by a Hamiltonian path. They also give a number of
relevant references.

Victor Miller
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Thu Jan 08, 2009 9:55 pm | All times are GMT
Forum index » Science and Technology » Math » Research
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts A Combinatorics/Graph Theory Question mathlover Undergraduate 1 Wed Jul 19, 2006 11:30 pm
No new posts A Combinatorics/Graph Theory Question mathlover Math 2 Wed Jul 19, 2006 11:02 pm
No new posts A Combinatorics/Graph Theory Question mathlover Combinatorics 0 Wed Jul 19, 2006 10:58 pm
No new posts Apparent Bug In "Permutations" Functi... Mark Lawton Symbolic 2 Sat Jul 15, 2006 11:31 am
No new posts Groups: Even/Odd Permutations Chris Smith Math 4 Fri Jul 14, 2006 4:02 am

Cell Phones | Mortgage Calculator | Mortgages | Credit Cards | Mortgage Calculator
Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.3904s ][ Queries: 16 (0.3150s) ][ GZIP on - Debug on ]