Intersections and Representations of Graphs

Given two graphs G and H sharing the same vertex set, the edge-intersection spectrum of G and H is the set of possible sizes of the intersection of the edge sets of both graphs. For example, the spectrum of two copies of the cycle C5 is {0, 2, 3, 5}, and the spectrum of two copies of the star K1,r is {1, r}. The intersection spectrum was initially studied for designs by Lindner and Fu and others and was originally extended to graphs by Eric Mendelsohn. Several examples are studied, both when G and H are isomorphic and when they are not isomorphic. It will also be shown any set S of positive integers is the edge-intersection spectrum of some pair of connected graphs. The other two chapters cover the area of conflict-tolerance graph representations. These representations consist of rules for measuring the rank and tolerance of each vertex, and for determining if two vertices are in conflict, by combining and comparing the ranks and tolerances of the vertices. The edge set of the graph is then the pairs of vertices which are in conflict. In the odd-intersection interval model, each vertex is represented by a subpath of a host path P, and two vertices are in conflict if and only if their corresponding subpaths intersect in an odd number of nodes. This model is not universal; in particular, the complete 4-partite graph K3,3,3,3 is a minimal forbidden subgraph. The parity of the subpaths affects the representation; graphs in which the subpaths are of a fixed odd order are strongly chordal (in fact, these are precisely the unit interval graphs), and graphs in which the subpaths are all of even order are bipartite. The converse of the latter statement is not true, as it will be shown that the number of bipartite graphs is asymptotically larger than the number of possible representations. A cross-comparison graph model\u3c\italic\u3e is one in which each vertex v is assigned a rank rv and a tolerance tv, and two vertices u and v are in conflict if rv ≥ tu and ru ≥ tv. Jamison showed that the cross-comparison model is universal, using n-dimensional vectors and coordinatewise comparison to represent a graph on n vertices. The inefficiency of a vector representation is the smallest number of dimensions d for which we can represent a graph G using d-dimensional vectors. The set of all graphs which can be represented using one-dimensional vectors (efficient cross-comparison graphs) is precisely the set of graphs which are the complement of a threshold tolerance graph (known as co-TT graphs; these were defined by Monma, Reed, and Trotter in 1988). The efficient cross-comparison graphs are characterized as those graphs which are chordal, and contain no strongly asteroidal triple --- a set of three vertices, such that there is a path between any two of these vertices which contains no neighbor of the third, and which does not contain two consecutive vertices adjacent to every neighbor of the third. In addition, a graph with a d-dimensional vector representation is the intersection of d efficient graphs. The inefficiency of G is bounded below by its chordality, and above by its boxicity; both of these bounds are tight. In addition, the graph Kn(2) has chordality and boxicity (and thus inefficiency) equal to n, and this is known to be the upper bound for boxicity, which shows that the efficiency of a graph is at most half its order, and that this bound is tight