7
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach

      Preprint

      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest integer k for which G has a distinguishing k-labeling. In this paper, we apply the principle of inclusion-exclusion and develop recursive formulas to count the number of inequivalent distinguishing k-labelings of a graph. Along the way, we prove that the distinguishing number of a planar graph can be computed in time polynomial in the size of the graph.}

          Related collections

          Author and article information

          Journal
          30 March 2007
          Article
          math/0703927
          7db09804-5ce2-47e4-bb47-f1878fdb610e
          Custom metadata
          05C78, 05C85
          27 pages
          math.CO cs.DS

          Comments

          Comment on this article