Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.