• Title of article

    Signed 2-independence in digraphs

  • Author/Authors

    Volkmann، نويسنده , , Lutz، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2012
  • Pages
    7
  • From page
    465
  • To page
    471
  • Abstract
    Let D be a finite and simple digraph with vertex set V ( D ) , and let f : V ( D ) → { − 1 , 1 } be a two-valued function. If ∑ x ∈ N − [ v ] f ( x ) ≤ 1 for each v ∈ V ( D ) , where N − [ v ] consists of v and all vertices of D from which arcs go into v , then f is a signed 2-independence function on D . The sum f ( V ( D ) ) is called the weight w ( f ) of f . The maximum of weights w ( f ) , taken over all signed 2-independence functions f on D , is the signed 2-independence number α s 2 ( D ) of D . s work, we mainly present upper bounds on α s 2 ( D ) , as for example α s 2 ( D ) ≤ n − 2 ⌈ Δ − / 2 ⌉ and α s 2 ( D ) ≤ Δ + + 1 − 2 ⌈ δ − 2 ⌉ Δ + + 1 ⋅ n , where n is the order, Δ − and δ − are the maximum and the minimum indegree and Δ + is the maximum outdegree of the digraph D . Some of our theorems imply well-known results on the signed 2-independence number of graphs.
  • Keywords
    Digraph , Oriented graph , Signed 2-independence function , Signed 2-independence number
  • Journal title
    Discrete Mathematics
  • Serial Year
    2012
  • Journal title
    Discrete Mathematics
  • Record number

    1599822