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

Simple item page
dc.creatorArvind, V.
dc.creatorCheng, Christine T.
dc.creatorDevanur, Nikhil R.
dc.date2007-03-30
dc.date.accessioned2026-07-07T08:08:53Z
dc.date.available2026-07-07T08:08:53Z
dc.descriptionA 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.}
dc.description27 pages
dc.identifierhttps://arxiv.org/abs/math/0703927
dc.identifierhttp://arxiv.org/abs/math/0703927
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/131414
dc.subjectCombinatorics
dc.subjectData Structures and Algorithms
dc.subject05C78, 05C85
dc.titleOn Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach
dc.typetext

Files

Collections

arXiv