Even orientations of graphs.

Domenico Labbate
Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata - Potenza (Italy)

Marien Abreu
Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata - Potenza (Italy)

John Sheehan
Department of Mathematical Sciences, King's College, Aberdeen (Scotland)

PDF

Minisymposium: GENERAL SESSION TALKS

Content: A graph $G$ is $1$--extendable if every edge belongs to at least one $1$--factor. %An orientation of a graph $G$ is an assignment of a {\em direction} to each %edge of $G$. Now suppose that Let $G$ be a graph with a $1$--factor $F$. Then an {\em even $F$--orientation} of $G$ is an orientation in which each $F$--alternating cycle has exactly an even number of edges directed in the same fixed direction around the cycle. We examine the structure of $1$--extendible graphs $G$ which have no even $F$--orientation where $F$ is a fixed $1$--factor of $G$ and we give a characterization for $k$--regular graphs with $k\ge 3$ and graphs with connectivity at least four. Moreover, we will point out a relationship between our results on even orientations and Pfaffian graphs.

Back to all abstracts