Join and Powers of Some Wedge Graphs as Segment Intersection Graph

Abstract

In graph theory, we can always make a graph representation of a collection of objects. This is commonly done with “intersection graphs", in which every vertex is defined as a collection of objects and the two vertices are adjacent if their collections intersect. A segment intersection graph (SEG) is an intersection graph of a non-empty family L of line segments in the plane denoted by Ω(L ) whose vertex-set is L where there is an edge between two vertices ℓ1 and ℓ2 in L if ℓ1 ∩ ℓ2 ≠∅. If L is a family of half-lines, Ω (L ) is called a half-line intersection graph. It is known that recognition of such graphs is NPhard. Here, we consider an intersection graph of half-lines contained in an arbitrarily thin θ-slice of the plane (the convex subset of R2 bounded by two half-lines with a common end-point and making an angle of θ (radians) with each other, 0 < θ < π called wedge graphs (WEDG). We show that wedge graphs are segment intersection graphs and unit segment intersection graphs. In particular, we prove that the join and powers of some paths, cycles, fans and wheels are wedge graphs and consequently, segment intersection graphs.