Abstract
Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 2879-2893 |
| Number of pages | 15 |
| Journal | Linear Algebra and Its Applications |
| Volume | 432 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - Jun 1 2010 |
| Externally published | Yes |
Keywords
- Algebraic connectivity
- Domination number
- Extremal graph
- Laplacian
ASJC Scopus subject areas
- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Fingerprint
Dive into the research topics of 'A sharp upper bound on algebraic connectivity using domination number'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS