• Title of article

    Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two

  • Author/Authors

    Lu، نويسنده , , Junjie and Wu، نويسنده , , Yaokun، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    5
  • From page
    841
  • To page
    845
  • Abstract
    Let S be any set of points in the Euclidean plane R 2 . For any p = ( x , y ) ∈ S , put S W ( p ) = { ( x ′ , y ′ ) ∈ S : x ′ < x and y ′ < y } and N E ( p ) = { ( x ′ , y ′ ) ∈ S : x ′ > x and y ′ > y } . Let G S be the graph with vertex set S and edge set { p q : N E ( p ) ∩ N E ( q ) ≠ 0̸ and S W ( p ) ∩ S W ( q ) ≠ 0̸ } . We prove that the graph H with V ( H ) = { u , v , z , w , p , p 1 , p 2 , p 3 } and E ( H ) = { u v , v z , z w , w u , p 1 p 3 , p 2 p 3 , p u , p v , p z , p w , p p 1 , p p 2 , p p 3 } and the graph H ′ obtained from H by removing the edge p p 3 are both minimal forbidden subgraphs for the class of graphs of the form G S .
  • Keywords
    Double competition graph , Poset of dimension at most two , Minimal forbidden subgraph
  • Journal title
    Applied Mathematics Letters
  • Serial Year
    2009
  • Journal title
    Applied Mathematics Letters
  • Record number

    1525968