{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T15:49:31Z","timestamp":1761752971766,"version":"build-2065373602"},"reference-count":0,"publisher":"University of Calgary","issue":"2","license":[{"start":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:00:00Z","timestamp":1761609600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Contrib Discrete Math"],"abstract":"<jats:p>A graph $G$ is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erd\u0151s and R\u00e9nyi (1963). They suggested the problem of starting with an asymmetric graph and removing some number $r$ of edges and\/or adding some number $s$ of edges so that the resulting graph is nonasymmetric. Erd\u0151s and R\u00e9nyi defined the degree of asymmetry of a graph to be the minimum value of $r+s$. In this paper, we define another property that measures how close a given nonasymmetric graph is to being asymmetric. We define the asymmetric index of a graph $G$, denoted $ai(G)$, to be the minimum of $r+s$ so that the resulting graph $G$ is asymmetric.\nWe investigate the asymmetric index of both connected and disconnected graphs. We prove that for any nonnegative integer $k$, there exists a graph $G$ where $ai(G)=k$. We show that the asymmetric index of a cycle with at least six vertices is two, and provide a complete characterization of all possible pairs of edges that can be added to a cycle to create an asymmetric graph. In addition we determine the asymmetric index of paths, certain circulant graphs, Cartesian products involving paths and cycles, and bounds for complete graphs, and complete bipartite graphs.<\/jats:p>","DOI":"10.55016\/ojs\/cdm.v20i2.69074","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T15:46:42Z","timestamp":1761752802000},"page":"508-523","source":"Crossref","is-referenced-by-count":0,"title":["The asymmetric index of a graph"],"prefix":"10.55016","volume":"20","author":[{"given":"Darren","family":"Narayan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandra","family":"Brewer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Gregory","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quindel","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalie","family":"Gomez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emma","family":"Farnsworth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herlandt","family":"Lino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"13844","published-online":{"date-parts":[[2025,10,28]]},"container-title":["Contributions to Discrete Mathematics"],"original-title":[],"link":[{"URL":"https:\/\/cdm.ucalgary.ca\/article\/download\/69074\/58579","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/cdm.ucalgary.ca\/article\/download\/69074\/58579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T15:46:43Z","timestamp":1761752803000},"score":1,"resource":{"primary":{"URL":"https:\/\/cdm.ucalgary.ca\/article\/view\/69074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,28]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,10,28]]}},"URL":"https:\/\/doi.org\/10.55016\/ojs\/cdm.v20i2.69074","relation":{},"ISSN":["1715-0868"],"issn-type":[{"value":"1715-0868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,28]]}}}