Endomorphism breaking in graphs

zbMATH Open1300.05100arXiv1311.6972MaRDI QIDQ405090FDOQ405090

Authors: Wilfried Imrich, Rafał Kalinowski, Florian Lehner, Monika Pilśniak 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We introduce the {it endomorphism distinguishing number} $D_e(G)$ of a graph $G$ as the least cardinal $d$ such that $G$ has a vertex coloring with $d$ colors that is only preserved by the trivial endomorphism. This generalizes the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined for automorphisms instead of endomorphisms. As the number of endomorphisms can vastly exceed the number of automorphisms, the new concept opens challenging problems, several of which are presented here. In particular, we investigate relationships between $D_e(G)$ and the endomorphism motion of a graph $G$, that is, the least possible number of vertices moved by a nontrivial endomorphism of $G$. Moreover, we extend numerous results about the distinguishing number of finite and infinite graphs to the endomorphism distinguishing number. This is the main concern of the paper.

Full work available at URL: https://arxiv.org/abs/1311.6972

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Bounds for distinguishing invariants of infinite graphs
• Breaking graph symmetries by edge colourings
• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishing Cartesian products of countable graphs
• The distinguishing index of infinite graphs

zbMATH Keywords

endomorphismsinfinite graphsdistinguishing number

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63) Ordinal and cardinal numbers (03E10)

Cites Work

• Title not available (Why is that?)
• Symmetry breaking in graphs
• Handbook of product graphs
• Asymmetric graphs
• On the minimum order of graphs with given semigroup
• The distinguishing number of Cartesian products of complete graphs
• Distinguishing maps
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• A note on the asymptotic and computational complexity of graph distinguishability
• Distinguishing infinite graphs
• Distinguishing labellings of group action on vector spaces and graphs
• Motion and distinguishing number two
• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishability of infinite groups and graphs

Cited In (6)

• The distinguishing index of infinite graphs
• Distinguishing threshold of graphs
• Endomorphism spectra of graphs
• Distinguishing graphs by edge-colourings
• The list distinguishing number of Kneser graphs
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring

This page was built for publication: Endomorphism breaking in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405090)