The maximum Laplacian separators of bicyclic and tricyclic graphs

doi:10.3969/j.issn.0253-2778.2017.09.004

Journal of University of Science and Technology of China ›› 2017, Vol. 47 ›› Issue (9): 733-737.DOI: 10.3969/j.issn.0253-2778.2017.09.004

• Original Paper • Previous Articles Next Articles

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

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

CLC Number:

O157.5

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.

References

［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)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments