The Asymmetric Index of a Graph

MaRDI QIDQ6306047zbMATH OpenFDO

Authors Alejandra Brewer, Adam Gregory, Quindel Jones, Darren Narayan

Publication date 30 August 2018

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: A graph $G$ is asymmetric if its automorphism group of vertices is trivial. Asymmetric graphs were introduced by ErdH{o}s and R'{e}nyi in 1963 where they measured the degree of asymmetry of an asymmetric graph. They proved that any asymmetric graph can be made non-asymmetric by removing some number $r$ of edges and/or adding adding some number $s$ of edges, and defined the degree of asymmetry of a graph to be the minimum value of $r+s$. In this paper, we define another property that how close a given non-asymmetric graph is to being asymmetric. We define the asymmetric index of a graph $G$, denoted $ai(G)$, to be the minimum of $r+s$ in order to change $G$ into an asymmetric graph.

This page was built for publication: The Asymmetric Index of a Graph

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