Edge-determining sets and determining index

DOI10.2140/INVOLVE.2024.17.85MaRDI QIDQ6197637zbMATH OpenOpenAlexFDO

Authors Sally Cockburn, Sean McAvoy

Publication date 20 March 2024

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.14122

zbMATH Keywords

determining numberdistinguishing indexhypercubes

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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 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${(}^{\prime }G)$. We prove that Det${(}^{\prime }G)leextDet(G)le2ext{D}^{\prime }et(G)$ when Det$(G)eq1$ 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.

Recommendations

• Identifying graph automorphisms using determining sets
• Graphs of order n with determining number n-3
• The determining number of a Cartesian product
• The determining number of Kneser graphs

Cites work

• A bound for the distinguishing index of regular graphs
• A graph which is edge transitive but not arc transitive
• Destroying automorphisms by fixing nodes
• Graph derivatives
• The chromatic distinguishing index of certain graphs
• The determining number of a Cartesian product
• The distinguishing index of connected graphs without pendant edges
• The distinguishing number and the distinguishing index of line and graphoidal graph(s)

This page was built for publication: Edge-determining sets and determining index

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