Download this article
 Download this article For screen
For printing
Recent Issues

Volume 17, 1 issue

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Author Index
Coming Soon
 
Other MSP Journals
Edge-determining sets and determining index

Sally Cockburn and Sean McAvoy

Vol. 17 (2024), No. 1, 85–106
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) Det (G) 2Det (G) when Det (G)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