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
Link To Document