An orientation theorem for graphs

A.M.H. Gerards

doi:10.1006/jctb.1994.1064

An orientation theorem for graphs

A.M.H. Gerards

Research output: Contribution to journal › Article › Academic › peer-review

6 Citations (Scopus)

Abstract

We characterize the class of graphs in which the edges can be oriented in such a way that going along any circuit in the graph, the number of forward edges minus the number of backward edges is equal to 0, 1, or -1. The result follows by applying Tutte's characterization of regular matroids to a certain binary matroid associated to a graph.

Original language	English
Pages (from-to)	199-212
Journal	Journal of Combinatorial Theory, Series B
Volume	62
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1994.1064
Publication status	Published - 1994

Access to Document

10.1006/jctb.1994.1064

Cite this

@article{9a50a4d00b634dcba398ba1952093f86,

title = "An orientation theorem for graphs",

abstract = "We characterize the class of graphs in which the edges can be oriented in such a way that going along any circuit in the graph, the number of forward edges minus the number of backward edges is equal to 0, 1, or -1. The result follows by applying Tutte's characterization of regular matroids to a certain binary matroid associated to a graph.",

author = "A.M.H. Gerards",

year = "1994",

doi = "10.1006/jctb.1994.1064",

language = "English",

volume = "62",

pages = "199--212",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - An orientation theorem for graphs

AU - Gerards, A.M.H.

PY - 1994

Y1 - 1994

N2 - We characterize the class of graphs in which the edges can be oriented in such a way that going along any circuit in the graph, the number of forward edges minus the number of backward edges is equal to 0, 1, or -1. The result follows by applying Tutte's characterization of regular matroids to a certain binary matroid associated to a graph.

AB - We characterize the class of graphs in which the edges can be oriented in such a way that going along any circuit in the graph, the number of forward edges minus the number of backward edges is equal to 0, 1, or -1. The result follows by applying Tutte's characterization of regular matroids to a certain binary matroid associated to a graph.

U2 - 10.1006/jctb.1994.1064

DO - 10.1006/jctb.1994.1064

M3 - Article

SN - 0095-8956

VL - 62

SP - 199

EP - 212

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

An orientation theorem for graphs

Abstract

Access to Document

Fingerprint

Cite this