Binary invariants and orientations of graphs
type: Item
instance of: scholarly article
title: Binary invariants and orientations of graphs
zbMATH Open document ID: 0771.05098
DOI: 10.1016/0012-365X(92)90607-H
author: G. Sabidussi
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
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''.
reviewed by: William G. Brown
Mathematics Subject Classification ID: 05E05
Mathematics Subject Classification ID: 13A50
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05A40
Mathematics Subject Classification ID: 15A72
zbMATH DE Number: 89907
zbMATH Keywords: symmetric function
zbMATH Keywords: Petersen problem
zbMATH Keywords: regular graph
zbMATH Keywords: induced invariant
zbMATH Keywords: orientations
zbMATH Keywords: 3-regular graphs
zbMATH Keywords: outdegree sequences
MaRDI profile type: Publication
cites work: Colorings and orientations of graphs
cites work: Zehnpunktige kubische Graphen
cites work: The invariant theory of binary forms
cites work: Julius Petersen 1839--1910. A biography
cites work: The one-hundredth anniversary of the death of invariant theory?
cites work: Correspondence between Sylvester, Petersen, Hilbert and Klein on invariants and the factorisation of graphs 1889--1891
description: scientific article; zbMATH DE number 89907