Page 123 - Textos de Matemática Vol. 39

OBSERVATIONS CONCERNING SPLIT GRAPHS 113
Problem 2. Prove or disprove the existence of infinitely many nondecom- posable Laplacian integral graphs.
The threshold completion problem (TCP) is to find the minimum number of edges whose addition to a given graph produces a threshold graph. The TCP is NP-complete on split graphs [16]. What if edges are not added but “adjusted”? Think of an edge as a “gate” hinged at two “posts”, and able to open at either. Such a gate might be “adjusted” if it is detached from one of its end posts, pivoted around the other, and reattached to some third post which may be an existing vertex of the graph or some new (previously isolated) vertex. To keep the problem “simple”, we require that the new configuration be a graph, i.e., contain no loops or multiple edges.
Problem 3. Find interesting general bounds on the minimum number of adjustments to the edges of a split graph necessary to produce a threshold graph.
Not every split partition is unigraphic. For example, at least five noniso- morphic graphs realize the split partition (52,42,22,12), no two of which are isospectral. (All five necessarily share the same chromatic polynomial.)
Problem 4. Find (interesting) inequalities that obtain among the spectra of nonisomorphic split graphs with the same degree sequence.
Among the many mathematical interests of E. M. de Sa´ is unimodular equivalence of integer matrices and the Smith normal form (SNF). (Results specific to the SNF of Laplacian matrices have been reported, e.g., in [1], [6], and [8].)
It is not hard to see that the SNF of the Laplacian of a hairy clique with n vertices, p of which have degree 1, is diag(1p+1, (n − p)n−p−2, 0), where exponents indicate multiplicities. Of the five graphs mentioned in connection with Problem 4, the Laplacians of two share SNF = diag(15, 5, 20, 0), two share SNF = diag(16, 99, 0), and the SNF of the remaining is diag(15, 4, 24, 0).
Problem 5. What graph theoretic properties influence the number of 1’s in the Smith normal form of the Laplacian matrix of a connected graph?
Problem 6. Can one tell from its Laplacian spectrum whether a graph is regular?