双圈图和三圈图的最大拉普拉斯分离度

doi:10.3969/j.issn.0253-2778.2017.09.004

中国科学技术大学学报 ›› 2017, Vol. 47 ›› Issue (9): 733-737.DOI: 10.3969/j.issn.0253-2778.2017.09.004

双圈图和三圈图的最大拉普拉斯分离度

余桂东，黄冬明，张午骁，汪宸

1. 安庆师范大学数学与计算科学学院,安徽安庆 246133； 2. 贵州大学数学与统计学院，贵州贵阳 550025

收稿日期:2016-03-14 修回日期:2016-12-29 接受日期:2016-12-29 出版日期:2023-03-27 发布日期:2016-12-29

The maximum Laplacian separators of bicyclic and tricyclic graphs

YU Guidong, HUANG Dongming, ZHANG Wuxiao,WANG Chen

1. School of Mathematics and Computation Sciences, Anqing Normal University, Anqing 246133, China; 2. School of Mathematics and Statistics, Guizhou University, Guiyang 550025, China

Received:2016-03-14 Revised:2016-12-29 Accepted:2016-12-29 Online:2023-03-27 Published:2016-12-29
Contact: YU Guidong
About author:YU Guidong(corresponding author), female, born in 1973, PhD/Prof. Research field: Graph theory. E-mail: guidongy@163.com
Supported by:
Supported by National Natural Science Foundation of China (11371028), NSF of Anhui Province (11040606M14), NSF of Department of Education of Anhui Province (KJ2015ZD27, KJ2017A362).

摘要/Abstract

摘要： 设G是一个n阶无向简单图,L(G)是G的拉普拉斯矩阵, 且μ1(G)≥μ2(G) ≥…≥μn(G)是L(G)的特征值. G的拉普拉斯分离度定义为SL(G)=μ1(G)-μ2(G).研究了给定阶数的双圈图和三圈图的最大拉普拉斯分离度，并刻画了相应的极图.

关键词: 双圈图, 三圈图, 图的拉普拉斯分离度, 拉普拉斯矩阵

Abstract: Let G be an undirected simple graph of order n, L(G) be the Laplacian matrix of G, and μ1(G)≥μ2(G) ≥…≥μn(G) be the eigenvalues of L(G). The Laplacian separator of G is defined as SL(G)=μ1(G)-μ2(G). Here the maximum Laplacian separators of bicyclic and tricyclic graphs of a given order were studied, and the corresponding extremal graphs were characterized.

Key words: bicyclic graph, tricyclic graph, Laplacian separator of graph, Laplacian matrix

中图分类号:

O157.5

余桂东, 黄冬明, 张午骁, 汪宸. 双圈图和三圈图的最大拉普拉斯分离度[J]. 中国科学技术大学学报, 2017, 47(9): 733-737.

YU Guidong, HUANG Dongming, ZHANG Wuxiao, WANG Chen. The maximum Laplacian separators of bicyclic and tricyclic graphs[J]. Journal of University of Science and Technology of China, 2017, 47(9): 733-737.

参考文献

［1］
HELLESETH T, KUMAR P V. Sequences with low correlation[C]// Handbook of Coding Theory. Amsterdam: Elsevier, 1998.
[2] LI N, TANG X H, HELLESETH T. New M-ary sequences with low autocorrelation from interleaved technique[J]. Des Codes Crytogr, 2014, 73: 237-249.
[3] DING C. Codes From Difference Sets[M]. Singapore: World Scientific, 2015.
[4] ZHU S X, WANG Y, SHI M J. Some results on cyclic codes over F2+vF2[J]. IEEE Trans Inform Theory, 2010, 56(4): 1680-1684.
[5] KUMAR P V, HELLESETH T, CALDERBANK A R. An upper bound for Weil exponential sums over Galois rings and applications[J]. IEEE Trans Inform Theory, 1995, 41(2): 456-468.
[6] KUMAR P V, HELLESETH T, CALDERBANK A R, et al. Large families of quaternary sequences with low correlation[J]. IEEE Trans Inform Theory, 1996, 42(2): 579-592.
[7] SHANBHAG A, KUMAR P V, HELLESETH T. Improved binary codes and sequences families from Z4-linear codes[J]. IEEE Trans Inform Theory, 1996, 42(5): 1582-1586.
[8] ZINOVIEV D V, SOL P. Quaternary codes and biphase sequences from Z8-codes[J]. Problems of Information Transmission, 2004, 40(2): 147-158 (translated from Problemy Peredachi Informatsii, 2004, 2: 50-62).
[9] HU H G, FENG D G, WU W L. Incomplete exponential sums over Galois rings with application to some binary sequences derived from Z2l[J]. IEEE Trans Inform Theory, 2006, 52(5): 2260-2265.
[10] LAHTONEN J, LING S, SOL P, ZINOVIEV D V. Z8-Kerdock codes and pseudo-random binary sequences[J]. J Complexity, 2004, 20: 318-330.
[11] WAN Z X. Finite Fields and Galois Rings[M]. Singapore: World Scientific, 2003.
[12] LIDL R, NIEDERREITER H. Finite Fields[M]. Cambridge, UK: Cambridge University Press, 1997.
[13] GOLOMB S W, GONG G. Signal Design for Good Correlation for Wireless Communication, Cryptography and Radar[M]. New York: Cambridge University Press, 2005.
[14] LING S, BLACKFORD J T. Zpk+1-linear codes[J]. IEEE Trans Inform Theory, 2002, 48(9): 2592-2605.
[15] HAMMONS A R Jr, KUMAR P V, CALDERBANK A R, et al. The Z4-linearity of Kerdock, Preparata, Goethals, and related codes[J]. IEEE Trans Inform Theory, 1994, 40(2): 301-309.

（上接第728页）

[20] ARKIN E M, HELD M, MITCHELL J S B, et al. Hamiltonian triangulations for fast rendering[J]. Visual Computer, 1996, 12(9):429-444.

[21] PAJAROLA R, ANTONIJUAN M, LARIO R. QuadTIN: Quadtree based triangulated irregular networks[C]// Proceedings of the Conference on Visualization 2002. IEEE, 2002: 395-402.

[22] TAUBIN G. Constructing Hamiltonian triangle strips on quadrilateral meshes[M]// Visualization and Mathematics III. Berlin: Springer, 2003: 69-91.

[23] GOPI M, EPPSTIEN D. Single-strip triangulation of manifolds with arbitrary topology[J]. Computer Graphics Forum, 2004, 23(3):371-379.

[24] DIAZ-GUTIERREZ P, BHUSHAN A, GOPI M, et al. Single-strips for fast interactive rendering[J]. Visual Computer, 2006, 22(6):372-386.

[25] GURUNG T, LUFFEL M, LINDSTROM P, et al. LR: compact connectivity representation for triangle meshes[J]. ACM Transactions on Graphics, 2011, 30(4):76-79.

[26] FLOATER M S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design, 1997, 14(3): 231-250.

双圈图和三圈图的最大拉普拉斯分离度

The maximum Laplacian separators of bicyclic and tricyclic graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价