The fixing number of a graph is the order of the smallest subset of its vertex set such that assigning distinct labels to all of the vertices in that subset results in the trivial automorphism; this is a recently introduced parameter that provides a measure of the non-rigidity of a graph. We provide a survey of elementary results about fixing numbers. We examine known algorithms for computing the fixing numbers of graphs in general and algorithms which are applied only to trees. We also present and prove the correctness of new algorithms for both of those cases. We examine the distribution of fixing numbers of various classifications of graphs.

• This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.

Creator

• Greenfield, Kara Bernadette

Contributors

• Martin, Bill

Publisher

• Worcester Polytechnic Institute

Identifier

• E-project-042811-111159

Advisor

• Christopher, Peter R.

Year

• 2011

Date created

• 2011-04-28

Resource type

• Major Qualifying Project

Major

• Mathematical Sciences

Rights statement

• In Copyright