In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. An indifference graph is also the intersection graph of a set of unit intervals, or of properly nested intervals (intervals none of which contains any other one). Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.
Equivalent characterizations
A finite indifference graph may be equivalently characterized as:
The intersection graph of a set of unit intervals. The intersection graph of a set of intervals with the same length. The intersection graph of a set of intervals no two of which are nested (one containing the other). A claw-free interval graph. A graph that does not have an induced subgraph isomorphic to a claw K 1 , 3 {\displaystyle K_{1,3}} , net (a triangle with a degree-one vertex adjacent to each of the triangle vertices), sun (a triangle surrounded by three other triangles that each share one edge with the central triangle), or hole (cycle of length four or more). An incomparability graph of semiorder. An undirected graph that has a linear order such that, for every three vertices ordered u {\displaystyle u} – v {\displaystyle v} – w {\displaystyle w} , if u w {\displaystyle uw} is an edge then so are u v {\displaystyle uv} and v w {\displaystyle vw} . A graph with no astral triple, three vertices connected pairwise by paths that avoid the third vertex and also do not contain two consecutive neighbors of the third vertex. A graph in which each connected component contains a path in which each maximal clique of the component forms a contiguous sub-path. A graph whose vertices can be numbered in such a way that every shortest path forms a monotonic sequence. A graph whose adjacency matrix can be ordered in such a way that, in each row and each column, the nonzeros of the matrix form a contiguous interval adjacent to the main diagonal of the matrix. An induced subgraph of a power of a chordless path. A leaf power having a leaf root which is a caterpillar. For an infinite graph, some of these definitions may differ.
Properties Because it is a special case of an interval graph, an indifference graph has all the properties of an interval graph; in particular, it is a special case of a chordal graph and of a perfect graph. It is also a special case of a circle graph, something that is not true of an interval graph more generally. In the Erdős–Rényi model of random graphs, an n {\displaystyle n} -vertex graph whose number of edges is significantly less than n 2 / 3 {\displaystyle n^{2/3}} will be an indifference graph with high probability, whereas an n {\displaystyle n} -vertex graph whose number of edges is significantly more than n 2 / 3 {\displaystyle n^{2/3}} will not be an indifference graph with high probability. The bandwidth of an arbitrary graph G {\displaystyle G} is 1 {\displaystyle 1} less than the size of the maximum clique in an indifference graph that contains G {\displaystyle G} as a subgraph and is chosen to minimize the size of the maximum clique. This property parallels similar relations between pathwidth and interval graphs, and between treewidth and chordal graphs. A weaker notion of width, the clique-width, may be arbitrarily large on indifference graphs. However, any proper (i.e., strictly smaller) subclass of indifference graphs that is closed under induced subgraphs has an upper bound on the clique-width of its graphs. A connected indifference graph has a Hamiltonian path. An indifference graph has a Hamiltonian cycle if and only if it is biconnected. An indifference graph obeys the reconstruction conjecture: it is uniquely determined by its vertex-deleted subgraphs.
… excerpt ends here. Continue reading the full article.
