Endomorphism breaking in graphs

MaRDI QIDQ405090zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1311.6972, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p16

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

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)

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.

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

Cites work

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

Cited in

(6)

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

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)