A Characterization of Graphs With Interval Squares
J. Richard Lundgren, Sarah K. Merz, Craig W. Rasmussen · 1995
. The competition graph of a symmetric digraph D with a loop at each vertex is the square of the underlying graph of D with loops removed. In the interest of efficiently assigning radio frequencies in a communication network, we would like to determine which graphs have interval squares. Necessary and sufficient conditions on the graph G are given for G 2 to be interval for several large classes of graphs. We first discuss results related to the Fulkerson-Gross characterization of interval graphs. Second, we discuss necessary conditions involving forbidden subgraphs and consider why such an approach does not produce sufficient conditions. Open problems are also considered. 1. Introduction. The square of a graph G = (V; E), denoted G 2 , is a graph on the same vertex set V such that two vertices x and y are adjacent in the square if and only if there is a path of length one or two between x and y in G. Squares of graphs have been studied by Balakrishnan and Paulraja [1], [2], Laskar...