A Lower Bound for the Algebraic Connectivity of a Graph in Terms of the Domination Number

被引：0
作者：
Yi-Zheng Fan
Ying-Ying Tan
机构：
[1] Anhui University,School of Mathematical Sciences
[2] Anhui Jianzhu University,School of Mathematics and Physics
来源：
Acta Mathematicae Applicatae Sinica, English Series | 2018年 / 34卷
关键词：
graph; algebraic connectivity; domination number; 05C50;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We investigate how the algebraic connectivity of a graph changes by relocating a connected branch from one vertex to another vertex, and then minimize the algebraic connectivity among all connected graphs of order n with fixed domination number γ≤n+23\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma\leq\frac{n+2}{3}$$\end{document}, and finally present a lower bound for the algebraic connectivity in terms of the domination number. We also characterize the minimum algebraic connectivity of graphs with domination number half their order.
引用
收藏
页码：752 / 760
页数：8
相关论文
共 45 条
[1]  
de Abreu N.M.M.(2007)Old and new results on algebraic connectivity of graphs Linear Algebra Appl. 423 53-73
[2]  
Bapat R.B.(1998)Algebraic connectivity and the characteristic set of a graph Linear Multilinear Algebra 45 247-273
[3]  
Pati S.(1998)Extremizing algebraic connectivity subject to graph theoretic constraints Electron J. Linear Algebra 3 48-74
[4]  
Merris R.(2003)A new proof of Fiedler’s inequality on the algebraic connectivity of trees J. Math. Study 36 379-383
[5]  
Fallat S.(2008)Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread Linear Algebra Appl. 429 577-588
[6]  
Kirkland S.(2009)Laplacian eigenvalues of graphs with given domination number Asian- European J. Math. 2 71-76
[7]  
Fan Y.Z.(1973)Algebraic connectivity of graphs Czechoslovak Math. J. 23 298-305
[8]  
Fan Y.Z.(1975)A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory Czechoslovak Math. J. 25 619-633
[9]  
Wang Y.(1985)On graphs having domination number half their order Periodica Mathematica Hungarica 16 287-293
[10]  
Gao Y.B.(2008)A conjecture on the algebraic connectivity of connected graphs with fixed girth Discrete Math. 308 5702-5711
12345