dorsal/arxiv
View SchemaStructural and extremal properties of $l_1$-Fiedler value
| Authors | M. Rajesh Kannan, Rahul Roy |
|---|---|
| Categories | |
| ArXiv ID | 2601.05771vv1 |
| URL | https://arxiv.org/abs/2601.05771 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
The algebraic connectivity $a(G)$, defined as the second smallest eigenvalue of the Laplacian matrix $L(G)$, admits a well-known variational characterization involving the minimization of a quadratic form subject to an $\ell_{2}$-norm constraint. In a recent work, Andrade and Dahl (2024) proposed an analogous formulation based on the $\ell_{1}$-norm, leading to the introduction of a new graph parameter $b(G)$, referred to as the $l_1$-Fiedler value. In this article, we undertake a detailed investigation of the structural and extremal properties of $b(G)$. We first derive a Nordhaus--Gaddum type inequality for $b(G)$. For trees, we determine both global maximizer and minimizers of $b(G)$, and present extremal constructions for trees with prescribed diameter, maximum degree, and number of pendant vertices. We further establish a connection between $b(G)$ and Laplacian matrices, and obtain a bound for $b(G)$ in terms of the edge connectivity, along with a complete characterization of the graphs attaining equality. We derive an explicit formula that describes the behaviour of $b(G)$ under the addition of pendant vertices. We also investigate the connection between $b(G)$ and the isoperimetric number.
{
"annotation_id": "21d15bf2-ea8e-4462-89b7-0d88875f5a2d",
"date_created": "2026-02-17T05:53:04.323000Z",
"date_modified": "2026-02-17T05:53:04.323000Z",
"file_hash": "0b55ebb125a3a753151d7ac6d5df432c98335a1c1325db052e90ce94aa9d03c6",
"private": false,
"record": {
"abstract": "The algebraic connectivity $a(G)$, defined as the second smallest eigenvalue of the Laplacian matrix $L(G)$, admits a well-known variational characterization involving the minimization of a quadratic form subject to an $\\ell_{2}$-norm constraint. In a recent work, Andrade and Dahl (2024) proposed an analogous formulation based on the $\\ell_{1}$-norm, leading to the introduction of a new graph parameter $b(G)$, referred to as the $l_1$-Fiedler value. In this article, we undertake a detailed investigation of the structural and extremal properties of $b(G)$. We first derive a Nordhaus--Gaddum type inequality for $b(G)$. For trees, we determine both global maximizer and minimizers of $b(G)$, and present extremal constructions for trees with prescribed diameter, maximum degree, and number of pendant vertices. We further establish a connection between $b(G)$ and Laplacian matrices, and obtain a bound for $b(G)$ in terms of the edge connectivity, along with a complete characterization of the graphs attaining equality. We derive an explicit formula that describes the behaviour of $b(G)$ under the addition of pendant vertices. We also investigate the connection between $b(G)$ and the isoperimetric number.",
"arxiv_id": "2601.05771",
"authors": [
"M. Rajesh Kannan",
"Rahul Roy"
],
"categories": [
"math.CO"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Structural and extremal properties of $l_1$-Fiedler value",
"url": "https://arxiv.org/abs/2601.05771",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "34fdc8b0-6138-44a5-aba0-d1141cf79a6b",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}