Title of article :
On an interpolation property of outerplanar graphs
Author/Authors :
Ko-Wei Lih، نويسنده , , Chen-Ying Lin، نويسنده , , Li-Da Tong، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Abstract :
Let D be an acyclic orientation of a graph G. An arc of D is said to be dependent if its reversal creates a directed cycle. Let image denote the number of dependent arcs in D. Define image (image) to be the minimum (maximum) number of image over all acyclic orientations D of G. We determine image for an outerplanar graph G and prove that G has an acyclic orientation with exactly k dependent arcs if image.
Keywords :
Dependent arc , Outerplanar graph , Interpolation property , Acyclic orientation
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics