Six signed Petersen graphs, and their automorphisms

DOI10.1016/J.DISC.2011.12.010zbMATH Open1239.05086arXiv1303.3347OpenAlexW1994722261MaRDI QIDQ411664FDOQ411664

Authors: Thomas Zaslavsky 

Publication date: 30 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Up to switching isomorphism there are six ways to put signs on the edges of the Petersen graph. We prove this by computing switching invariants, especially frustration indices and frustration numbers, switching automorphism groups, chromatic numbers, and numbers of proper 1-colorations, thereby illustrating some of the ideas and methods of signed graph theory. We also calculate automorphism groups and clusterability indices, which are not invariant under switching. In the process we develop new properties of signed graphs, especially of their switching automorphism groups.

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

Recommendations

• The chromatic polynomials of signed Petersen graphs
• The number of switching isomorphism classes of signed graphs associated with particular graphs
• Non-isomorphic signatures on some generalised Petersen graph
• Signatures and signed switching classes
• Edge coloring of the signed generalized Petersen graph

zbMATH Keywords

balanceclusterabilitysigned graphPetersen graphswitchingfrustrationproper graph coloringswitching automorphism

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Cites Work

• Signed graphs
• Signed graph coloring
• On the notion of balance of a signed graph
• Title not available (Why is that?)
• Correlation clustering
• Biased graphs. I: Bias, balance, and gains
• Title not available (Why is that?)
• Inside-out polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Chromatic invariants of signed graphs
• Characterizations of signed graphs
• Title not available (Why is that?)

Cited In (6)

• Open problems in the spectral theory of signed graphs
• On the distance spectra of product of signed graphs
• SIGNED COMPLETE GRAPHS ON SIX VERTICES AND THEIR FRUSTRATION INDICES
• Combinatorics of Petersen graph and its compositions for all irreducible representations for Jahn-Teller, non-rigid molecules and clusters
• The number of switching isomorphism classes of signed graphs associated with particular graphs
• Non-isomorphic signatures on some generalised Petersen graph

This page was built for publication: Six signed Petersen graphs, and their automorphisms

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