Binary invariants and orientations of graphs

DOI10.1016/0012-365X(92)90607-HMaRDI QIDQ1197033zbMATH OpenFDO

Authors G. Sabidussi

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)90607-H

zbMATH Keywords

3-regular graphsinduced invariantorientationsoutdegree sequencesPetersen problemregular graphsymmetric function

Mathematics Subject Classification ID

Umbral calculus (05A40) Graph theory (05C99) Symmetric functions and generalizations (05E05) Actions of groups on commutative rings; invariant theory (13A50) Vector and tensor algebra, theory of invariants (15A72)

Review text

Julius Petersen posed the following problem: (L'Intermédiaire des Mathématicens 1 (1894), p.\ 24, Problem 66) ``Soit \(u_ 0=(x_ 1-x_ 2)^ \alpha(x_ 1-x_ 3)^ \beta(x_ 2-x_ 3)^ \gamma... (x_{n- 1}-x_ n)^ \mu\) une expression où les exposants \(\alpha\), \(\beta\), \(...\), sont des entiers positifs, ou zéro; \(u_ 0\) étant du même degré en \(x_ 1,x_ 2,...,x_ n\). De \(u_ 0\) déduisons \(u_ 1,u_ 2,...\) en faisant toutes les permutations possibles entre \(x_ 1,x_ 2,...,x_ n\). La somme \(u_ 0+u_ 1+...\) est une fonction symétrique de \(x_ 1,x_ 2,...,x_ n\) qui peut être identiquement nulle. Est-il possible de trouver des conditions simples que doive remplir \(u_ 0\) pour que cela ait lieu? The present author interprets the problem as ``of the type: Given a regular graph and a property of its induced invariant, what can be said about the graph? ... In \S3 we discuss the connection between the vanishing of the induced invariant and properties of the orientations of the graph. On the basis of a classical result about the existence of invariants of degree 3 we then show that the answer to Question 66 is negative (\S4). \S5 is devoted to orientations of 3-regular graphs. The existence or non-existence of `odd reorientations' (reversals of an odd number of edges) which preserve all outdegree sequences is dealt with by invariant theoretical means as well as purely graph theoretical ones. The final section contains some remarks about a class of orientations whose presence ensures that the graph induces a nonvanishing invariant.

Recommendations

• The odd-even invariant for graphs
• An orientation theorem for graphs
• On sign-invariance graphs of uniform oriented matroids
• scientific article; zbMATH DE number 691480
• scientific article; zbMATH DE number 17787

Cites work

• Colorings and orientations of graphs
• Correspondence between Sylvester, Petersen, Hilbert and Klein on invariants and the factorisation of graphs 1889--1891
• Julius Petersen 1839--1910. A biography
• The invariant theory of binary forms
• The one-hundredth anniversary of the death of invariant theory?
• Zehnpunktige kubische Graphen

Cited in

(6)

• Julius Petersen 1839--1910. A biography
• Determination of many-electron basis functions for a quantum Hall ground state using Schur polynomials
• Quantum Hall ground states and regular graphs
• List edge colourings of some 1-factorable multigraphs
• Discriminants, Symmetrized Graph Monomials, and Sums Of Squares
• Semi-invariants of binary forms and symmetrized graph-monomials

This page was built for publication: Binary invariants and orientations of graphs

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