English

运筹学学报 >

2017 , Vol. 21 >Issue 1: 103 - 110

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.01.010

运筹学

基于拉普拉斯谱确定的两类树

展开
  • 1. 上海大学理学院数学系, 上海 200444; 2. 武警政治学院, 上海 201602

收稿日期: 2016-07-08

  网络出版日期: 2017-03-15

基金资助

国家自然科学基金(No. 11371242)

收起

Two families of trees determined by  their Laplacian spectrum

Expand
  • 1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China; 2. PAP Institute of Politics, Shanghai 201602, China

Received date: 2016-07-08

  Online published: 2017-03-15

Fold

摘要

设图G是简单连通图. 如果任何一个与图G关于拉普拉斯矩阵同谱的图, 都与图G同构, 称图G可由其拉普拉斯谱确定. 定义了树Y_n和树F(2,n,1)两类特殊结构的树. 利用同谱图线图的特点, 证明了树Y_n和树F(2,n,1)可由其拉普拉斯谱确定.

关键词： 图谱; 同谱图; 特征值; 拉普拉斯谱

本文引用格式

张涛, 白延琴 . 基于拉普拉斯谱确定的两类树[J]. 运筹学学报, 2017 , 21(1) : 103 -110 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.010

Abstract

Let G be a simple connected graph. A graph G is called to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G. In this paper, tree Y_n and tree F(2,n,1) which have special structures are defined. It is proved that these two families of trees are determined by their Laplacian spectrum, considering the properties of the line graphs of  the cospectral graphs.

Key words： spectrum of a graph; cospectral graphs; eigenvalue; Laplacian spectrum

参考文献

[1] Van Dam E R, Haemers W H. Which graphs are determined by their spectrum [J]. Linear Algebra Appl, 2003, 373: 241-272.
[2] Doob M, Haemers W H. The complement of the path is determined by its spectrum [J]. Linear Algebra Appl, 2002, 356: 57-65.
[3] Dragos M, Cvetkovic, Michael D, Horst S.   Spectra of Graphs: Theory and Applications [M].  Heidelberg;  Leipzig: Barth, 1976.
[4] Bondy J A, Murty U S R. Graph Theory with Application [M]. New York: The MacMillan Press, 1976.
[5] Oliveira C S, Deabreu N M M, Jurkiewilz S. The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes [J].  Linear Algebra Appl, 2002, 356: 113-121.
[6] Kelmans A K. The number of trees of a graph Ⅰ [J]. Automat i Telemah, 1965, 26: 2154-2204.
[7] Kelmans A K. The number of trees of a graph Ⅱ [J].  Automat i Telemah, 1966, 27: 56-65.
[8] Kelmans A K. Characteristic polynomial and the number of spanning trees of graphs and their optimization [D]. t Lectrures at the All-union Workshop on Graph Theory, Vaivary, Latviiskiy Gos Universitet, 1972.
[9] Kelmans A K , Chelnokov V M. A certain polynomial of a graph and graphs with an extremal numbers of trees [J]. Journal of Combinatorial Theory, Series B, 1974, 16: 197-214.
[10] Li J S, Zhang X D. On the Laplacian eigenvalues of a graph [J]. Linear Algebra Appl, 1998, 285: 305-307.
[11] Gutman I, Gineityte V, Lepovic M, et al. The high-energy band in the photoelectron spectrum of alkanes and its dependence on molecular structure [J]. J Serb Chem Soc, 1999, 64: 673-680.
[12] Harary F. Graph Theory [M]. Addison Wesley, 1969.
[13] 沈小玲, 侯耀平. 一些由它的 Laplacian 谱确定的树 [J]. 湖南师范大学自然科学学报, 2006, 29(1): 21-24.
Options
文章导航

/

〈 〉