Algebraic connectivity of connected graphs with fixed number of pendant vertices

DOI10.1007/S00373-010-0975-0zbMATH Open1235.05089arXiv1003.4646OpenAlexW1976232023MaRDI QIDQ659677FDOQ659677

Authors: Arbind Kumar Lal, Kamal L. Patra, Binod K. Sahoo 

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: In this paper we consider the following problem: Over the class of all simple connected graphs of order $n$ with $k$ pendant vertices ($n,k$ being fixed), which graph maximizes (respectively, minimizes) the algebraic connectivity? We also discuss the algebraic connectivity of unicyclic graphs.

Full work available at URL: https://arxiv.org/abs/1003.4646

Recommendations

• Maximizing Algebraic Connectivity Over Unicyclic Graphs
• Extremizing algebraic connectivity subject to graph theoretic constraints
• Minimizing algebraic connectivity over graphs made with some given blocks
• Algebraic connectivity of trees with the maximum degree
• The algebraic connectivity of graphs with given stability number

zbMATH Keywords

Laplacian matrixAlgebraic connectivityCharacteristic setPendant vertexPerron component

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Laplacian matrices of graphs: A survey
• Title not available (Why is that?)
• The Laplacian Spectrum of a Graph
• Minimizing algebraic connectivity over connected graphs with fixed girth
• Extremizing algebraic connectivity subject to graph theoretic constraints
• Title not available (Why is that?)
• A conjecture on the algebraic connectivity of connected graphs with fixed girth
• The ordering of trees and connected graphs by algebraic connectivity
• Title not available (Why is that?)
• Algebraic connectivity and the characteristic set of a graph
• Characteristic vertices of trees^*
• Maximizing Algebraic Connectivity Over Unicyclic Graphs
• Characteristic vertices of weighted trees via perron values
• The effect on the algebraic connectivity of a tree by grafting or collapsing of edges
• Maximizing the distance between center, centroid and characteristic set of a tree
• Perron components and algebraic connectivity for weighted graphs

Cited In (11)

• On the distance Laplacian spectra of graphs
• Trees with matrix weights: Laplacian matrix and characteristic-like vertices
• A conjecture on the algebraic connectivity of connected graphs with fixed girth
• On the spectral gap of a quantum graph
• First eigenvalue of nonsingular mixed graphs with given number of pendant vertices
• Algebraic connectivity of \(k\)-connected graphs.
• Minimizing algebraic connectivity over graphs made with some given blocks
• Hamiltonian graphs of given order and minimum algebraic connectivity
• Ordering trees and graphs with few cycles by algebraic connectivity
• The algebraic connectivity of barbell graphs
• The algebraic connectivity of graphs with given matching number

This page was built for publication: Algebraic connectivity of connected graphs with fixed number of pendant vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659677)