On split graphs with four distinct eigenvalues

被引：8

作者：

Goldberg, Felix ^{[1
]}

Kirkland, Steve ^{[2
]}

Varghese, Anu ^{[3
]}

Vijayakumar, Ambat ^{[4
]}

机构：

[1] Univ Haifa, Caesarea Rothschild Inst, Haifa, Israel

[2] Univ Manitoba, Dept Math, Winnipeg, MB, Canada

[3] Bishop Chulaparambil Mem Coll, Dept Math, Kottayam, Kerala, India

[4] Cochin Univ Sci & Technol, Dept Math, Cochin, Kerala, India

来源：

DISCRETE APPLIED MATHEMATICS | 2020年 / 277卷

基金：

爱尔兰科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

Adjacency matrix; Split graph; Bidegreed graph; Combinatorial design;

D O I：

10.1016/j.dam.2019.09.016

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is a well-known fact that a graph of diameter d has at least d +1 eigenvalues. A graph is d-extremal, if it has diameter d and exactly d + 1 eigenvalues. A graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have diameter at most 3. We obtain a complete classification of the connected bidegreed 3-extremal split graphs using the association of split graphs with combinatorial designs. We also construct certain families of non-bidegreed 3-extremal split graphs. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：163 / 171

页数：9

共 21 条

[1]

[Anonymous], 2001, Graduate Texts in Mathematics

[2] ALMOST ALL CHORDAL GRAPHS SPLIT [J].

BENDER, EA ;

RICHMOND, LB ;

WORMALD, NC .

JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1985, 38 (APR) :214-221

[3]

Brouwer A.E., 2012, UNIVERSITEXT, V223

[4] Variations on a theorem of Ryser [J].

Cao, DS ;

Chvatal, V ;

Hoffman, AJ ;

Vince, A .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1997, 260 :215-222

[5]

Colburn C.J., 2006, The CRC Handbook of Combinatorial Designs, CRC Press Series on Discrete Mathematics and its Applications

[6]

Cvetkovic D., 1997, ENCY MATH ITS APPL, V66

[7]

Cvetkovic D.M, 1980, SPECTRA GRAPHS THEOR

[8]

Doob M., 1970, LINEAR ALGEBRA APPL, V3, P461

[9] On the spectrum of an extremal graph with four eigenvalues [J].

Fiol, M. A. ;

Garriga, E. .

DISCRETE MATHEMATICS, 2006, 306 (18) :2241-2244

[10] Characterization of split graphs with at most four distinct eigenvalues [J].

Ghorbani, Modjtaba ;

Azimi, Nasrin .

DISCRETE APPLIED MATHEMATICS, 2015, 184 :231-236

← 1 2 3 →