• Title of article

    On an interpolation property of outerplanar graphs

  • Author/Authors

    Ko-Wei Lih، نويسنده , , Chen-Ying Lin، نويسنده , , Li-Da Tong، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2006
  • Pages
    7
  • From page
    166
  • To page
    172
  • 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
  • Serial Year
    2006
  • Journal title
    Discrete Applied Mathematics
  • Record number

    886186