• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Graph Distinguishability and the Generation of Non-Isomorphic Labellings

Bird, William Herbert 26 August 2013 (has links)
A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers. / Graduate / 0984 / 0405 / bbird@uvic.ca

Page generated in 0.0935 seconds