On algebraic connectivity augmentation |
| |
Authors: | Steve Kirkland Claudia Marcela Justel |
| |
Affiliation: | a National University of Ireland Maynooth, Ireland b School of Statistical Sciences, Rio de Janeiro, Brazil c Instituto Militar de Engenharia, Rio de Janeiro, Brazil |
| |
Abstract: | Suppose that G is an undirected graph, and that H is a spanning subgraph of Gc whose edges induce a subgraph on p vertices. We consider the expression α(G∪H)-α(G), where α denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on α(G∪H)-α(G) in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression α(G∪H)-α(G) in the interval [0,p]. A bound on α(G∪H)-α(G) is provided in a special case, and several examples are considered. |
| |
Keywords: | Graph Laplacian matrix Algebraic connectivity |
本文献已被 ScienceDirect 等数据库收录! |
|