Trees with distinguishing index equal distinguishing number plus one
Copyright policy )Trees with distinguishing index equal distinguishing number plus one
The distinguishing number (index) $D(G)$ ($D'(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex (edge) labeling with $d$ labels that is preserved only by the trivial automorphism. It is known that for every graph $G$ we have $D'(G) \leq D(G) + 1$. In this note we characterize trees for which this inequality is sharp. We also show that if $G$ is a connected unicyclic graph, then $D'(G) = D(G)$.
9 pages
- University of Warwick United Kingdom
- University of Ljubljana Slovenia
- University of Maribor Slovenia
- UNIVERZA V LJUBLJANI Slovenia
- University of Ljubljana, Faculty of Mathematics and Physics Slovenia
automorphism group, tree, Trees, 05C15, 05E18, Group actions on combinatorial structures, 05e18, Coloring of graphs and hypergraphs, distinguishing index, 05c15, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), unicyclic graph, Mathematics, distinguishing number
automorphism group, tree, Trees, 05C15, 05E18, Group actions on combinatorial structures, 05e18, Coloring of graphs and hypergraphs, distinguishing index, 05c15, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), unicyclic graph, Mathematics, distinguishing number
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!