时间：2022-09-29 01:37:09
摘要研究超图的标号性质，首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界；其次构造与超图对应的简单图，通过其拉普拉斯矩阵的特征值给出超图带宽的下界.
关键词超图；带宽和；带宽；割宽；特征值
中图分类号O 157.5文献标识号A
所有可能的标号函数ψ.其它未说明的术语和记号可参见文献[1].
超图的带宽和、带宽与割宽等问题是超大规模集成电路布线设计、编码理论等领域提出的实际问题的图论表示，它们都与超图顶点集V （H）的一个最优标号有关.即使对简单图，这些问题都是NP？完全的[2]，所以在超图中也没有好的算法.在工业应用中，多用启发式算法[3，4]作近似计算，这时一个好的上界或下界对判定算法的优劣就很有必要.
本文主要工作是首先利用拉普拉斯张量的第二小和最大Z-特征值给出4-超图带宽和以及割宽的上下界；其次构造与超图对应的简单图，通过其拉普拉斯矩阵的第二小和最大特征值，给出超图带宽的下界.
参考文献
[1]贝尔热.超图.南京：东南大学出版社， 2002.
[2] Garey M R， Johnson D S， Stockmeyer L. Some simplified NP-complete graph problems. Theoretical Computer Science， 1976， 1： 237-267.
[3] Bhasker J， Sahni S. Optimal arrangement of circuit components. J VLSI Comput Syst， 1987， 2（1）： 87-109.
[4] Kang S. Linear ordering and application to placement. Proc 20thDesign Automation Conference， 1983， 457-463.
[5] Qi Liqun. Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation， 2005， 40： 1302-1324.
[6] Lim Lek-Heng. Singular values and eigenvalues of a tensor： a variational approach. Proceedings of the IEEE International Workshop on Computational Advances in MultiSensor Adaptive Processing， 2005， 1： 129-132.
[7] Xie Jinshan， Chang An. A new type of Laplacian tensor and its Z-eigenvalues of an even uniform hypergraph. International Journal of Applied Mathematics and Statistics， 2013， 31（1）： 9-19.
[8]谢锦山.关于图与超图的若干谱问题研究.福州：福州大学离散数学研究中心， 2012.
[9] Juvan M， Mohar B. Laplace eigenvalues and bandwidth-type invariants of graphs. Journal of Graph Theory， 1990， 17（3）： 393-407.