On the eigenvalues of certain Cayley graphs and arrangement graphs

被引：15

作者：

Chen, Bai Fan ^{[1
]}

Ghorbani, Ebrahim ^{[2
,3
]}

Wong, Kok Bin ^{[1
]}

机构：

[1] Univ Malaya, Inst Math Sci, Kuala Lumpur 50603, Malaysia

[2] KN Toosi Univ Technol, Dept Math, Tehran, Iran

[3] Inst Res Fundamental Sci IPM, Sch Math, Tehran, Iran

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2014年 / 444卷

关键词：

Arrangement graph; Cayley graph; Symmetric group; Spectrum integrality; SPECTRA;

D O I：

10.1016/j.laa.2013.11.035

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we show that the eigenvalues of certain classes of Cayley graphs are integers. The (n, k, r)-arrangement graph A (n, k, r) is a graph with all the k-permutations of an n-element set as vertices where two k-permutations are adjacent if they differ in exactly r positions. We establish a relation between the eigenvalues of the arrangement graphs and the eigenvalues of certain Cayley graphs. As a result, the conjecture on integrality of eigenvalues of A(n, k, 1) follows. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：246 / 253

页数：8

共 23 条

[1]

Abdollahi A, 2009, ELECTRON J COMB, V16

[2] SPECTRA OF CAYLEY GRAPHS [J].

BABAI, L .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (02) :180-189

[3]

Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6

[4]

Chapuy G., ARXIV12024976V2

[5]

Chen BF, 2013, ELECTRON J COMB, V20

[6] The edge-centered surface area of the arrangement graph [J].

Cheng, Eddie ;

Qiu, Ke ;

Shen, Zhizhang .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (01) :49-64

[7] The number of shortest paths in the arrangement graph [J].

Cheng, Eddie ;

Grossman, Jerrold W. ;

Qiu, Ke ;

Shen, Zhizhang .

INFORMATION SCIENCES, 2013, 240 :191-204

[8] Linearly many faults in arrangement graphs [J].

Cheng, Eddie ;

Liptak, Laszlo ;

Yuan, Allen .

NETWORKS, 2013, 61 (04) :281-289

[9] Conditional matching preclusion for the arrangement graphs [J].

Cheng, Eddie ;

Lipman, Marc J. ;

Liptak, Laszlo ;

Sherman, David .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (45) :6279-6289

[10] On the arrangement graph [J].

Chiang, WK ;

Chen, RJ .

INFORMATION PROCESSING LETTERS, 1998, 66 (04) :215-219

← 1 2 3 →