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 条
  • [1] Median eigenvalues of bipartite graphs
    Mohar, Bojan
    Tayfeh-Rezaie, Behruz
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2015, 41 (03) : 899 - 909
  • [2] On the eigenvalues of complete bipartite signed graphs
    Pirzada, Shariefuddin
    Shamsher, Tahir
    Bhat, Mushtaq A.
    ARS MATHEMATICA CONTEMPORANEA, 2024, 24 (04)
  • [3] Regular bipartite graphs with three distinct non-negative eigenvalues
    Koledin, Tamara
    Stanic, Zoran
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 438 (08) : 3336 - 3349
  • [4] On the Eigenvalues Distribution in Threshold Graphs
    Zhenzhen Lou
    Jianfeng Wang
    Qiongxiang Huang
    Graphs and Combinatorics, 2019, 35 : 867 - 880
  • [5] On the Eigenvalues Distribution in Threshold Graphs
    Lou, Zhenzhen
    Wang, Jianfeng
    Huang, Qiongxiang
    GRAPHS AND COMBINATORICS, 2019, 35 (04) : 867 - 880
  • [6] Graph invertibility and median eigenvalues
    Ye, Dong
    Yang, Yujun
    Mandal, Bholanath
    Klein, Douglas J.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 513 : 304 - 323
  • [7] MORE ON NON-REGULAR BIPARTITE INTEGRAL GRAPHS WITH MAXIMUM DEGREE 4 NOT HAVING ±1 AS EIGENVALUES
    de Abreu, Nair M. M.
    Balinska, Krystyna T.
    Simic, Slobodan K.
    Zwierzynski, Krzysztof T.
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2014, 8 (01) : 123 - 154
  • [8] Bipartite Steinhaus graphs
    Lee, YS
    Chang, GJ
    TAIWANESE JOURNAL OF MATHEMATICS, 1999, 3 (03): : 303 - 310
  • [9] On the determinant of bipartite graphs
    Bibak, Khodakhast
    DISCRETE MATHEMATICS, 2013, 313 (21) : 2446 - 2450
  • [10] On the Aα-Eigenvalues of Signed Graphs
    Pasten, Germain
    Rojo, Oscar
    Medina, Luis
    MATHEMATICS, 2021, 9 (16)