Extremal Problems Involving the Two Largest Complementarity Eigenvalues of a Graph

被引:0
作者
Alberto Seeger
David Sossa
机构
[1] University of Avignon,Department of Mathematics
[2] Universidad de O’Higgins,Instituto de Ciencias de la Ingeniería
来源
Graphs and Combinatorics | 2020年 / 36卷
关键词
Complementarity eigenvalue; Connected graph; Spectral radius; Second largest complementarity eigenvalue; Connected induced subgraph; Graph perturbation; 05C50; 15A42;
D O I
暂无
中图分类号
学科分类号
摘要
This paper deals with various extremal problems involving two important parameters associated to a connected graph, say G. The first parameter is the largest complementarity eigenvalue: it is denoted by ϱ(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varrho (G)$$\end{document} and it is simply the spectral radius or index of the graph. Next in importance comes the second largest complementarity eigenvalue: it is denoted by ϱ2(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varrho _2(G)$$\end{document} and it is equal to the largest spectral radius among the children of G. By definition, a child or vertex-deleted connected subgraph of G is an induced subgraph obtained by removing a noncut vertex from G. In the first part of this work, we address the problem of identifying the eldest children and the youngest parents of G. We also analyze the uniqueness of such children and parents. An eldest child of G is a child whose spectral radius attains the value ϱ2(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varrho _2(G)$$\end{document}. The concept of youngest parent is somewhat dual to that of eldest child. The second part of this work is about minimization and maximization of the functions ϱ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varrho _2$$\end{document} and ϱ-ϱ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varrho -\varrho _2$$\end{document} on special classes of connected graphs. We establish several new results and propose a number of conjectures.
引用
收藏
页码:1 / 25
页数:24
相关论文
共 34 条
  • [1] Brualdi R(1986)On the spectral radius of connected graphs Publ. Inst. Math. (Beograd), Nouvelle série tome 39 53 45-54
  • [2] Solheid E(1957)Spektren endlicher Grafen Abh. Math. Sem. Univ. Hamburg 21 63-77
  • [3] Collatz L(2017)Complementarity eigenvalue of graphs Linear Algebra Appl. 527 216-231
  • [4] Sinogowitz U(1979)Generalized Ramsey theory for graphs. X. Double stars Discrete Math. 28 247-254
  • [5] Fernandes R(1971)Cospectral graphs and digraphs Bull. Lond. Math. Soc. 3 321-328
  • [6] Judice J(2007)On the spectral radius of unicyclic graphs with fixed diameter Linear Algebra Appl. 420 449-457
  • [7] Trevisan V(1973)On the eigenvalues of trees Period. Math. Hungar. 3 175-182
  • [8] Grossman JW(1982)The second largest eigenvalue of a tree Linear Algebra Appl. 46 9-25
  • [9] Harary F(2014)Indices for special classes of trees Linear Algebra Appl. 442 106-114
  • [10] Klawe M(2010)Cone-constrained eigenvalue problems: theory and algorithms Comput. Optim. Appl. 45 25-57