Structural and extremal properties of l 1 l_{1} -Fiedler value
M. Rajesh Kannan, Rahul Roy · 2026
Read Structural and extremal properties of l 1 l_{1} -Fiedler value by M. Rajesh Kannan, Rahul Roy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05771.txt.
Introduction
M Rajesh Kannan and Rahul Roy investigate in 2026 a newer measure of graph connectedness called the l1-Fiedler value. The classical algebraic connectivity uses the second smallest Laplacian eigenvalue and an l2 constraint. A recent variational version replaces that constraint with an l1 norm, producing the parameter they study.
The authors derive a Nordhaus-Gaddum type inequality relating the value on a graph and its complement. For trees they find which shapes maximize and minimize the value, including trees with fixed diameter, maximum degree, or pendant vertex count. They connect the parameter to Laplacian matrices, bound it through edge connectivity, and characterize the graphs where equality holds. A formula describes how adding pendant vertices changes the value.
Catalog record
| CREATOR | M. Rajesh Kannan, Rahul Roy |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05771
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structural and extremal properties of l 1 l_{1} -Fiedler value M. Rajesh Kannan, Rahul Roy Abstract The algebraic connectivity a ( G ) a(G) , defined as the second smallest eigenvalue of the Laplacian matrix L ( G ) L(G) , admits a well-known variational characterization involving the minimization of a quadratic form subject to an ℓ 2 \ell_{2} -norm constraint. In a recent work, Andrade and Dahl (2024) proposed an analogous formulation based on the ℓ 1 \ell_{1} -norm, leading to the introduction of a new graph parameter b ( G ) b(G) , referred to as the l 1 l_{1} -Fiedler value. In this article, we undertake a detailed investigation of the structural and extremal properties of b ( G ) b(G) . We first derive a Nordhaus–Gaddum type inequality for b ( G ) b(G) . For trees, we determine both global maximizer and minimizers of b ( G ) 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 ) b(G) and Laplacian matrices, and obtain a bound for b ( G ) 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 ) b(G) under the addition of pendant vertices. We also investigate the connection between b ( G ) b(G) and the isoperimetric number. 1 Introduction The eigenvalues and eigenvectors of Laplacian matrices of graphs play a fundamental role in spectral graph theory and have found wide-ranging applications in areas such as combinatorial optimization, electrical networks, graph signal processing, data science, and machine learning. In particular, the second smallest eigenvalue of the Laplacian matrix serves as a robust measure of the connectivity of a graph [ 6 ] . It also provides useful lower or upper bounds for several important graph invariants, including the isoperimetric number, maximum cut, independence number, genus, and diameter [ 10 , 11 , 13 ] . The associated eigenvector plays a central role in graph partitioning and data clustering, most notably in spectral clustering methods [ 13 , 14 ] . In his seminal work [ 6 ] , Fiedler introduced the term algebraic connectivity to describe the second smallest Laplacian eigenvalue. The algebraic connectivity of a graph G , denoted by a(G) , admits a well-known variational characterization involving the l_{2} -norm in the objective function and the constraints. More recently, in [ 1 ] , Andrade and Dahl investigated analogous optimization formulations based on the l_{1} -norm and the l_{\infty} -norm. The resulting parameters are denoted by b(G) and \gamma(G) , respectively. They established a formula for b(G) in terms of the sparsest cut of G , which implies that computing b(G) is an NP-hard problem. In contrast, they showed that \gamma(G) can be computed via a linear programming formulation. Let G=(V(G),E(G)) be an unweighted, undirected, and simple graph. The set V(G) contains the vertices, and E(G) contains the edges of G . The number of vertices, written as |V(G)| , is n . If two vertices u and v are adjacent, we write u\sim v . The adjacency matrix of G , denoted by A(G) , is the symmetric n\times n matrix whose (u,v) -entry is defined as a_{uv}=\begin{cases}1,&\text{if }u\sim v,\\[4.0pt] 0,&\text{otherwise}.\end{cases} For a graph G , let \Delta(G) denote the diagonal matrix with the degrees of the vertices of G as its diagonal elements. The Laplacian matrix L(G) is the n\times n matrix defined as L(G)=\Delta(G)-A(G), The eigenvalues of the adjacency matrix help in understanding several structural properties of a graph, such as whether it is bipartite or regular. They also give bounds for important graph parameters, including the chromatic number, clique number, and independence number [ 2 ] . The eigenvalues of the Laplacian matrix of a graph reveal information about the connectedness of the graph G . It is well known that G is connected if and only if a(G)>0 [ 6 , 7 ] . An eigenvector corresponding to a(G) is called a Fiedler vector [ 1 ] . The value a(G) can be computed using a standard optimization formula based on the Courant–Fischer theorem [ 8 ] . This formula is: a(G)=\min\biggl\{\sum_{uv\in E(G)}(x_{u}-x_{v})^{2}:\sum_{v\in V(G)}x_{v}=0~\mbox{and}~\|x\|_{2}=1\ \biggl\}, where \|x\|_{2}:=\sqrt{\sum\limits_{i=1}^{n}|x_{i}|^{2}} is the l_{2} -norm of the vector x\in\mathbb{R}^{n} . The vector x that gives the minimum in this expression has an important property: the squared differences (x_{u}-x_{v})^{2} along the edges are as small as possible. This means that the values of x change in an optimal and smooth way across the edges of the graph. Andrade and Dahl [ 1 ] referred to this as the \ell_{2} -smoothing problem. They also studied similar optimization problems using the \ell_{1} -norm and the \ell_{\infty} -norm [ 1 ] . This led to the definition of two new graph parameters: b(G)=\min\biggl\{\sum_{uv\in E(G)}|x_{u}-x_{v}|:\sum_{v\in V(G)}x_{v}=0~\mbox{and}~\|x\|_{1}=1\biggl\}, \gamma(G)=\min\biggl\{\max_{uv\in E(G)}|x_{u}-x_{v}|:\sum_{v\in V(G)}x_{v}=0~\mbox{and}~\|x\|_{\infty}=1\biggl\}. Here, \|x\|_{1}:=\sum\limits_{i=1}^{n}|x_{i}| denotes the l_{1} -norm, and \|x\|_{\infty}:=\max\{|x_{i}|:1\leq i\leq n\} denotes the l_{\infty} -norm of the vector x\in\mathbb{R}^{n} . These optimization problems are well-defined because the constraint sets are compact and the objective functions are continuous. We refer to b(G) as the l_{1} -Fiedler value. The vectors that achieve the minima are called the \ell_{1} -Fiedler vector and the \ell_{\infty} -Fiedler vector, respectively. The main objective of this article is to further investigate the quantity b(G) . We first establish a bound on b(G) in terms of the number of vertices and edges of a graph (Theorem 3.1 ). Using this result, we derive a Nordhaus–Gaddum type bound for b(G) (Theorem 3.3 ). For trees, we identify the global maximizer and minimizers for b(G) (Theorem 4.2 ), and construct extremal examples for trees with prescribed diameter (Theorem 4.3 ), maximum degree (Theorem 4.4 ), and number of pendant vertices (Theorem 4.5 ). A connection between b(G) and the Laplacian matrices of graphs is established in Theorem 5.1 . We then obtain a bound for b(G) in terms of the edge connectivity of G (Theorem 6.1 ), and provide a complete characterization of the graphs for which this bound is sharp (Theorem 6.2 ). Next, we derive a formula describing the change in b(G) under the addition of pendent vertices (Theorem 6.3 ). In Section 6.2 , we investigate the relationship between the isoperimetric number and the quantity b(G) . 2 Preliminary results We denote by K_{n},C_{n},P_{n}, and S_{n} the complete graph, cycle graph, path graph, and star graph on n vertices, respectively. The degree of a vertex v in a graph is denoted by \deg(v) . A vertex v of a graph G is called a pendant vertex if \deg(v)=1 . Let d_{\min}(G) denote the minimum vertex degree of G , and d_{\max}(G) is the maximum degree of any vertex in G . A graph G is said to be regular if all its vertices have the same degree. That is, d_{\max}(G)=d_{\min}(G) . The average degree of a graph G , denoted by d_{\avg}(G) , is the average of the degrees of all the vertices in G . It is given by: d_{\avg}(G)=\frac{1}{|V(G)|}\sum\limits_{u\in V(G)}\deg(u).