On fully orientability of 2-degenerate graphs
Resource
Information Processing Letters 105 (5): 177-181
Journal
Information Processing Letters
Journal Volume
105
Journal Issue
5
Pages
177-181
Date Issued
2008
Author(s)
Abstract
Suppose that D is an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let d (D) denote the number of dependent arcs in D. Define dmin (G) (dmax (G)) to be the minimum (maximum) number of d (D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying dmin (G) ≤ k ≤ dmax (G). We prove that every 2-degenerate graph is fully orientable and give interpretations to their dmin. © 2007 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
02.pdf
Size
24.16 KB
Format
Adobe PDF
Checksum
(MD5):1a2bb95411cc7b98cd44d0fff25d9b7c