Removing Twins in Graphs to Break Symmetries

Antonio González and María Luz Puertas
Additional contact information
Antonio González: Departamento de Didáctica de las Matemáticas, Universidad de Sevilla, 41013 Sevilla, Spain
María Luz Puertas: Departamento de Matemáticas and Agrifood Campus of International Excellence (ceiA3), Universidad de Almería, 04120 Almería, Spain

Mathematics, 2019, vol. 7, issue 11, 1-13

Abstract: Determining vertex subsets are known tools to provide information about automorphism groups of graphs and, consequently about symmetries of graphs. In this paper, we provide both lower and upper bounds of the minimum size of such vertex subsets, called the determining number of the graph. These bounds, which are performed for arbitrary graphs, allow us to compute the determining number in two different graph families such are cographs and unit interval graphs.

Keywords: graph; automorphism group; determining number; cograph; unit interval graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/11/1111/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/11/1111/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:11:p:1111-:d:287486

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().