On a Problem of Eric Mendelsohn on Edge-Intersections 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 path P_n is {0,1,..., n - 1}, and the spectrum of two copies of the star K_(1,r) is {l,r}. The intersection spectrum was initially studied for designs by Lindner and Pu and others, and was originally extended to graphs by E. Mendelsohn. We will examine the spectra of several types of graphs, both when G = H and when G not =H, and show that any set of distinct positive integers always can be obtained as the intersection spectrum of two graphs.