Six signed Petersen graphs, and their automorphisms

DOI10.1016/J.DISC.2011.12.010MaRDI QIDQ411664zbMATH OpenOpenAlexFDO

Authors Thomas Zaslavsky

Publication date 30 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• scientific article; zbMATH DE number 3252056 (Why is no real title available?)
• scientific article; zbMATH DE number 3020563 (Why is no real title available?)
• Biased graphs. I: Bias, balance, and gains
• Characterizations of signed graphs
• Chromatic invariants of signed graphs
• Correlation clustering
• Inside-out polytopes
• On the notion of balance of a signed graph
• Signed graph coloring
• Signed graphs

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)