Edge-determining sets and determining index

Cockburn, Sally; McAvoy, Sean

doi:10.2140/involve.2024.17.85

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Edge-determining sets and determining index

Sally Cockburn and Sean McAvoy

Vol. 17 (2024), No. 1, 85–106

DOI: 10.2140/involve.2024.17.85

Abstract

A graph automorphism is a bijective mapping of the vertices that preserves adjacent vertices. A vertex-determining set of a graph is a set of vertices such that the only automorphism that fixes those vertices is the identity. The size of a smallest such set is called the determining number, denoted by $Det (G)$ . The determining number is a parameter of the graph capturing its level of symmetry. We introduce the related concept of an edge-determining set and determining index, ${Det}^{'} (G)$ . We prove that ${Det}^{'} (G) \leq Det (G) \leq 2 {Det}^{'} (G)$ when $Det (G) \neq 1$ and show both bounds are sharp for infinite families of graphs. Further, we investigate properties of these new concepts, as well as provide the determining index for several families of graphs, including hypercubes.

Keywords

determining number, distinguishing index, hypercubes

Mathematical Subject Classification

Primary: 05C25

Secondary: 05C70

Milestones

Received: 29 July 2022

Revised: 30 December 2022

Accepted: 30 December 2022

Published: 15 March 2024

Communicated by Anant Godbole

Authors

Sally Cockburn
Mathematics and Statistics Department Hamilton College Clinton, NY United States

Sean McAvoy
Department of Statistics University of California Berkeley, CA United States

Vol. 17, No. 1, 2024