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

distinguishing numberendomorphismsinfinite graphs

Mathematics Subject Classification ID

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

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.

Review text

Summary: We introduce the 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.

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

• 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
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• 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)

• The list distinguishing number of Kneser graphs
• The distinguishing index of infinite graphs
• Distinguishing graphs by edge-colourings
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• Distinguishing threshold of graphs
• Endomorphism spectra of 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)