Median eigenvalues of bipartite graphs

被引:0
|
作者
Bojan Mohar
Behruz Tayfeh-Rezaie
机构
[1] Simon Fraser University,Department of Mathematics
[2] Institute for Research in Fundamental Sciences (IPM),School of Mathematics
来源
Journal of Algebraic Combinatorics | 2015年 / 41卷
关键词
Adjacency matrix; Graph eigenvalues; Median eigenvalues; Covers; 05C50;
D O I
暂无
中图分类号
学科分类号
摘要
For a graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} of order n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} and with eigenvalues λ1⩾⋯⩾λn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _1\geqslant \cdots \geqslant \lambda _n$$\end{document}, the HL-index R(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(G)$$\end{document} is defined as R(G)=max|λ⌊(n+1)/2⌋|,|λ⌈(n+1)/2⌉|.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(G) ={\max }\left\{ |\lambda _{\lfloor (n+1)/2\rfloor }|, |\lambda _{\lceil (n+1)/2\rceil }|\right\} .$$\end{document} We show that for every connected bipartite graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} with maximum degree Δ⩾3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \geqslant 3$$\end{document}, R(G)⩽Δ-2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R(G)\leqslant \sqrt{\Delta -2}$$\end{document} unless G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is the the incidence graph of a projective plane of order Δ-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta -1$$\end{document}. We also present an approach through graph covering to construct infinite families of bipartite graphs with large HL-index.
引用
收藏
页码:899 / 909
页数:10
相关论文
共 50 条
  • [41] On the limit points of the smallest positive eigenvalues of graphs
    Barik, Sasmita
    Mondal, Debabrota
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2025, 715 : 1 - 16
  • [42] On the eigenvalues of Laplacian ABC-matrix of graphs
    Rather, Bilal Ahmad
    Ganie, Hilal A.
    Li, Xueliang
    QUAESTIONES MATHEMATICAE, 2023, 46 (11) : 2403 - 2419
  • [43] Some signed graphs whose eigenvalues are main
    Shao, Zhenan
    Yuan, Xiying
    APPLIED MATHEMATICS AND COMPUTATION, 2022, 423
  • [44] ON THE INVERSE OF A CLASS OF BIPARTITE GRAPHS WITH UNIQUE PERFECT MATCHINGS
    Panda, S. K.
    Pati, S.
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2015, 29 : 89 - 101
  • [45] Inverse of Hermitian Adjacency Matrix of Mixed Bipartite Graphs
    Alomari, Omar
    COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2021, 2024, 448 : 287 - 293
  • [46] Maximum order of trees and bipartite graphs with a given rank
    Ghorbani, E.
    Mohammadian, A.
    Tayfeh-Rezaie, B.
    DISCRETE MATHEMATICS, 2012, 312 (24) : 3498 - 3501
  • [47] ON THE SECOND LARGEST SPECTRAL RADIUS OF UNICYCLIC BIPARTITE GRAPHS
    Nath, Milan
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2011, 3 (02) : 253 - 258
  • [48] Bipartite Distance-regular Graphs, Part I
    Brian Curtin
    Graphs and Combinatorics, 1999, 15 : 143 - 158
  • [49] On unicyclic non-bipartite graphs with tricyclic inverses
    Kalita, Debajit
    Sarma, Kuldeep
    LINEAR & MULTILINEAR ALGEBRA, 2023, 71 (08): : 1378 - 1396
  • [50] LDPC Code Construction from Bipartite Kneser Graphs
    Chowdhury, Tamal
    Pramanik, Ankita
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON COMMUNICATION, DEVICES AND COMPUTING, 2020, 602 : 1 - 12