Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/15062
Title: Some new considerations about double nested graphs
Author: Andelic, M.
Andrade, E.
Cardoso, D. M.
Fonseca, C. M. da
Simic, S. K.
Tosic, D. V.
Keywords: Bipartite graph
Double nested graph
Largest eigenvalue
Spectral bounds
Main eigenvalue
Issue Date: 15-Oct-2015
Publisher: Elsevier
Abstract: In the set of all connected graphs with fixed order and size, the graphs with maximal index are nested split graphs, also called threshold graphs. It was recently (and independently) observed in [F.K.Bell, D. Cvetkovi´c, P. Rowlinson, S.K. Simi´c, Graphs for which the largest eigenvalue is minimal, II, Linear Algebra Appl. 429 (2008)] and [A. Bhattacharya, S. Friedland, U.N. Peled, On the first eigenvalue of bipartite graphs, Electron. J. Combin. 15 (2008), #144] that double nested graphs, also called bipartite chain graphs, play the same role within class of bipartite graphs. In this paper we study some structural and spectral features of double nested graphs. In studying the spectrum of double nested graphs we rather consider some weighted nonnegative matrices (of significantly less order) which preserve all positive eigenvalues of former ones. Moreover, their inverse matrices appear to be tridiagonal. Using this fact we provide several new bounds on the index (largest eigenvalue) of double nested graphs, and also deduce some bounds on eigenvector components for the index. We conclude the paper by examining the questions related to main versus non-main eigenvalues.
Peer review: yes
URI: http://hdl.handle.net/10773/15062
DOI: 10.1016/j.laa.2015.06.010
ISSN: 0024-3795
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
matrix_tech.pdfartigo346 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.