The optimal general upper bound for the distinguishing index of infinite graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

The optimal general upper bound for the distinguishing index of infinite graphs

Authors:	Monika Pil?niak Marcin Stawiski

Institution:	Department of Discrete Mathematics, AGH University, Krakow, Poland

Abstract:	The distinguishing index $D' (G)$ of a graph $G$ is the least cardinal number $d$ such that $G$ has an edge-coloring with $d$ colors, which is preserved only by the trivial automorphism. We prove a general upper bound $D' ?≤? (G) \leq Δ ? 1$ for any connected infinite graph $G$ with finite maximum degree $Δ \geq 3$ . This is in contrast with finite graphs since for every $Δ \geq 3$ there exist infinitely many connected, finite graphs $G$ with $?,? D' (G) = Δ$ . We also give examples showing that this bound is sharp for any maximum degree $Δ$ .

Keywords:	automorphism distinguishing index edge-coloring infinite graph symmetry breaking in graph