The reversing number of a diagraph

Jean Pierre Barthélemy; Olivier Hudry; Garth Isaak; Fred S. Roberts; Barry Tesman

doi:10.1016/0166-218X(94)00042-C

The reversing number of a diagraph

Jean Pierre Barthélemy
, Olivier Hudry
, Garth Isaak
, Fred S. Roberts
, Barry Tesman

ENST Bretagne
Lehigh University
Rutgers University–New Brunswick
Dickinson College

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

16 Citations (Scopus)

Abstract

A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

Original language	English
Pages (from-to)	39-76
Number of pages	38
Journal	Discrete Applied Mathematics
Volume	60
Issue number	1-3
DOIs	https://doi.org/10.1016/0166-218X(94)00042-C
Publication status	Published - 23 Jun 1995
Externally published	Yes

Access to Document

10.1016/0166-218X(94)00042-C

Cite this

@article{0e0d7b3a2b8544c7be33cb32de2e0ba6,

title = "The reversing number of a diagraph",

abstract = "A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.",

author = "Barth{\'e}lemy, \{Jean Pierre\} and Olivier Hudry and Garth Isaak and Roberts, \{Fred S.\} and Barry Tesman",

year = "1995",

month = jun,

day = "23",

doi = "10.1016/0166-218X(94)00042-C",

language = "English",

volume = "60",

pages = "39--76",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - The reversing number of a diagraph

AU - Barthélemy, Jean Pierre

AU - Hudry, Olivier

AU - Isaak, Garth

AU - Roberts, Fred S.

AU - Tesman, Barry

PY - 1995/6/23

Y1 - 1995/6/23

N2 - A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

AB - A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

U2 - 10.1016/0166-218X(94)00042-C

DO - 10.1016/0166-218X(94)00042-C

M3 - Article

AN - SCOPUS:0043142525

SN - 0166-218X

VL - 60

SP - 39

EP - 76

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

The reversing number of a diagraph

Abstract

Access to Document

Fingerprint

Cite this