Intersection graph

Introduction to Graph Models

Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018

Jonathan L. Gross, Jay Yellen, Mark Anderson

definition: A simple graph G with vertex-set VG = {v1, v2…, vn} is an intersection graph if there exists a family of sets F = {S1, S2, …, Sn} such that vertex vi is adjacent to vj if and only if i ≠ j and Si∩Sj≠0.

On some inverse 1-center location problems

View Article

Journal Information

Published in Optimization, 2019

Kien Trung Nguyen, Nguyen Thanh Hung, Huong Nguyen-Thu, Tran Thu Le, Van Huy Pham

An interval graph is, by definition, the intersection graph of a family of intervals on the real line. Roughly speaking, each interval represents a vertex, say in V , for . Moreover, if , there exists an edge in E for . For applications of interval graphs, e.g. genetic structure, sequential storage, scheduling, seriation in archaeology, etc., one can see Golumbic [23] and references therein. We further assume that all edges of G have the length of 1 and each vertex is associated with a positive weight for . The interval graph G is connected if for any interval I there exists at least one interval which has nonempty intersection with I in the presentation of G. Moreover, a proper interval graph is an interval graph that has an interval representation in which no interval is properly contained in another interval. A proper interval graph can be recognized in linear time by Panda and Das [24]. From here after, we always assume that G is a proper connected interval graph. For illustration, we can observe a proper connected interval graph in Figure 1 which is presented by a class of intervals on the line as in Figure 2.

Intersection graph

Explore chapters and articles related to this topic

Introduction to Graph Models

On some inverse 1-center location problems