Structural and extremal properties of l1-Fiedler value

The algebraic connectivity 𝑎 ⁡ ( 𝐺 ) , defined as the second smallest eigenvalue of the Laplacian matrix 𝐿 ⁡ ( 𝐺 ) , admits a well-known variational characterization involving the minimization of a quadratic form subject to an ℓ 2 -norm constraint. In a recent work, Andrade and Dahl (2024) proposed an analogous formulation based on the ℓ 1 -norm, leading to the introduction of a new graph parameter 𝑏 ⁡ ( 𝐺 ) , referred to as the 𝑙 1 -Fiedler value. In this article, we undertake a detailed investigation of the structural and extremal properties of 𝑏 ⁡ ( 𝐺 ) . We first derive a Nordhaus–Gaddum type inequality for 𝑏 ⁡ ( 𝐺 ) . For trees, we determine both global maximizer and minimizers of 𝑏 ⁡ ( 𝐺 ) , and present extremal constructions for trees with prescribed diameter, maximum degree, and number of pendant vertices. We further establish a connection between 𝑏 ⁡ ( 𝐺 ) and Laplacian matrices, and obtain a bound for 𝑏 ⁡ ( 𝐺 ) in terms of the edge connectivity, along with a complete characterization of the graphs attaining equality. We derive an explicit formula that describes the behavior of 𝑏 ⁡ ( 𝐺 ) under the addition of pendant vertices. We also investigate the connection between 𝑏 ⁡ ( 𝐺 ) and the isoperimetric number.