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

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

2007-03-30

arxiv.org/abs/math/0703927v1

Mathematics

Combinatorics

27 pages

Scientific paper

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.}

Affiliated with

Also associated with

No associations

Rating

On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach 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 On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-651037