On the l ∞ l_{\infty} -analog of Algebraic Connectivity M. Rajesh Kannan, Rahul Roy Abstract The algebraic connectivity a ⁡ ( G ) a(G) of a graph G G is defined as the second smallest eigenvalue of its Laplacian matrix L ⁡ ( G ) L(G) . It also admits a variational characterization as the minimum of a quadratic form associated with L ⁡ ( G ) L(G) , subject to l 2 l_{2} -norm constraints. In 2024, Andrade and Dahl investigated an analogous parameter γ ⁡ ( G ) \gamma(G) , defined using the l ∞ l_{\infty} -norm instead of the l 2 l_{2} -norm. They demonstrated that γ ⁡ ( G ) \gamma(G) can be computed in polynomial time using linear programming. In this article, we study the combinatorial significance of γ ⁡ ( G ) \gamma(G) , revealing that it can be efficiently computed using a breadth-first search (BFS) algorithm. We show that γ ⁡ ( G ) \gamma(G) characterizes the connectedness of the graph G G . We further establish new bounds on γ ⁡ ( G ) \gamma(G) , and analyze the graphs that attain extremal values. Finally, we derive an elegant formula for γ ⁡ ( G ) \gamma(G) when G G is the Cartesian product of finitely many graphs. Applying this formula, we explicitly compute γ ⁡ ( G ) \gamma(G) for various families of graphs, including hypercube graphs, Hamming graphs, and others. AMS Subject Classification(2010): 05C12, 05C50, 05C76. Keywords. Algebraic connectivity, Distance matrix, Transmission, Cartesian product, l_{\infty} -norm. 1 Introduction The Laplacian matrices of graphs, along with their eigenvalues and eigenvectors, have found numerous applications in various domains, including combinatorial optimization, electrical networks, graph signal processing, data science, and machine learning. The second smallest eigenvalue of the Laplacian matrix provides a robust measure of the connectivity of the associated graph. It also serves as a lower or upper bound for several important graph parameters, such as the isoperimetric number, maximum cut, independence number, genus, and diameter [ 6 , 10 , 11 , 13 ] . The corresponding eigenvector is widely used in graph partitioning problems and data clustering, a method known as spectral clustering [ 13 , 14 ] . In his seminal paper [ 6 ] , Fiedler coined the term algebraic connectivity for the second smallest eigenvalue of the Laplacian matrix. The algebraic connectivity of a graph G , denoted by a(G) , has an interesting optimization characterization involving the l_{2} -norm in the objective function and the constraints. Recently, in [ 1 ] , Andrade and Dahl studied the counterparts of this optimization problem with respect to the l_{1} -norm and the l_{\infty} -norm. The corresponding optimal values are denoted by b(G) and \gamma(G) , respectively. They showed that b(G) has an interesting connection to the sparsest cut problem, implying that computing b(G) is an NP-hard problem. They also proposed a linear programming formulation to compute \gamma(G) . In this article, we provide an explicit combinatorial formula for \gamma(G) in terms of the maximum row sum of the distance matrix of G . This leads to a polynomial-time combinatorial algorithm for computing \gamma(G) . Further, we study the connections between \gamma(G) and various graph parameters associated with G . In addition, we derive a formula for \gamma(G) when G is the Cartesian product of finitely many graphs. Let G=(V(G),E(G)) be an unweighted, undirected, and simple graph, where V(G) is the set of vertices and E(G) is the set of edges of G . Let the number of vertices in G , denoted by |V(G)| , be n . If the vertex u is adjacent to the vertex v , then we write u\sim v . The adjacency matrix of a simple graph G , denoted by A(G) , is the symmetric n\times n matrix whose (u,v) -th entry is defined by a_{uv}=1 if u\sim v , and a_{uv}=0 otherwise. The Laplacian matrix L(G) is the n\times n matrix defined as L(G)=\Delta(G)-A(G), where \Delta(G) is the diagonal matrix with the degrees of the vertices of G as its diagonal elements, and A(G) is the adjacency matrix of G . The eigenvalues of adjacency matrices can be used to obtain various structural properties of graphs, such as bipartiteness, regularity, and more. Additionally, the eigenvalues of adjacency matrices provide bounds for several graph parameters, including the chromatic number, clique number, independence number, and others [ 3 , 7 , 12 , 15 ] . On the other hand, the eigenvalues of the Laplacian matrix of a graph reveal information about the connectedness of the graph G . In particular, 0 is always an eigenvalue of L(G) , with the all-ones vector as a corresponding eigenvector. The second smallest eigenvalue of L(G) , denoted by a(G) , is called the algebraic connectivity of the graph G [ 6 ] . It is well known that G is connected if and only if a(G)>0 . An eigenvector corresponding to a(G) is called a Fiedler vector [ 3 ] . The optimization approach to computing a(G) is well known and is based on the Courant-Fischer theorem [ 9 ] . An explicit formula for a(G) is given as follows: 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} . Note that the vector x that attains the minimum in the above optimization problem has the following property: the entries of x exhibit the minimum squared difference along the edges of the graph. This can be viewed as an ”optimal” variation along the edges of G . For this reason, Andrade and Dahl [ 1 ] referred to this as the l_{2} -smoothing problem. Furthermore, they investigated analogous problems under the l_{1} -norm and the l_{\infty} -norm, considering both the objective function and the constraint [ 1 ] . This led to the introduction of two new parameters, defined as follows: 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, as the minima are attained due to the compactness of the constraint sets and the continuity of the objective functions. The vectors that give the optimal solutions are referred to as the l_{1} - Fiedler vector and the l_{\infty} - Fiedler vector , respectively. Furthermore, they formulated the following linear programming problem to compute \gamma(G) . Let G be a graph with n vertices. For every k with 1\leq k\leq n , consider the linear programming problem LP(k) : Minimize \displaystyle y subject to \displaystyle x_{i}-x_{j}\leq y\quad(ij\in E(G)), \displaystyle-(x_{i}-x_{j})\leq y\quad(ij\in E(G)), \displaystyle\sum_{j=1}^{n}x_{j}=0, \displaystyle-1\leq x_{j}\leq 1\quad(1\leq j\leq n), \displaystyle x_{k}=1. Solving LP(k) for each 1\leq k\leq n , and choosing the minimum value of y obtained gives the value of \gamma(G) . The primary objective of this paper is to provide an elegant combinatorial expression for the quantity \gamma(G) in terms of the maximum row sum of the distance matrix of the graph G . Furthermore, in the case of trees, it suffices to consider only the maximum row sum corresponding to the pendant vertices. This is done in Section 3 . Next, in Section 4 , we establish bounds for \gamma(G) in terms of well-known graph-theoretic parameters, namely the distance spectral radius, Wiener index, algebraic connectivity, Cheeger constant, and others. We also study the corresponding extremal graphs. In Section 5 , we present the results on the Cartesian product of graphs in relation to \gamma(G) . 2 Preliminaries In this section, we recall some of the known definitions and results that will be used later. For a vertex u\in V(G) , let \deg(u) denote the degree of u in G . A vertex v of a graph G is called a pendant vertex , if \deg(v)=1 . The distance between two vertices u and v is denoted by d(u,v) . The diameter of a graph G , denoted by \diam(G) , is the maximum distance between any pair of vertices in G , that is, \diam(G)=\max_{u,v\in V(G)}d(u,v). Let u\in V(G) . Define S_{r}(u)=\biggl\{v\in V(G):d(u,v)=r\biggl\}. The distance matrix D(G) of a graph G is the n\times n matrix in which the (u,v) -entry D_{uv} is given by the distance d(u,v) between the vertices u and v . The spectrum of D(G) , denoted by \{\partial_{1}(G),\partial_{2}(G),\dots,\partial_{n}(G)\} , consists of the eigenvalues of D(G) arranged in non-increasing order, that is, \partial_{1}(G)\geq\partial_{2}(G)\geq\dots\geq\partial_{n}(G) . An n\times n matrix A is said to be cogredient to a matrix E if there exists a permutation matrix P such that PAP^{T}=E , where P^{T} denotes the transpose of the matrix P . A matrix A is called reducible if it is cogredient to a block matrix of the form: E=\begin{bmatrix}B&0\\ C&F\end{bmatrix}, where B and F are square matrices. Further, if n=1 and A=0 , then A is also considered reducible. Otherwise, A is called irreducible . The well-known Perron-Frobenius theorem states that if A is non-negative and irreducible, then the spectral radius \rho(A) is a simple eigenvalue of A and any eigenvalue of A that has the same modulus is also simple. Moreover, A admits a positive eigenvector x corresponding to \rho(A) , and every non-negative eigenvector of A is a scalar multiple of x . For more details about the Perron-Frobenius theory, we refer to [ 4 ] . It is easy to see that the distance matrix D(G) of a connected graph G is irreducible. Hence, by Perron-Frobenius theorem, we have \partial_{1}(G) is simple and there is an eigenvector corresponding to \partial_{1}(G) with strictly positive coordinates. The transmission of a vertex u\in V(G) , denoted by \tr(u) , is the sum of distances from u to all other vertices in G [ 2 ] . That is, \tr(u)=\sum_{v\in V(G)}d(u,v) A graph G is said to be transmission-regular , if \tr(v)=k for some k\in\mathbb{N} and for every vertex v in G . A graph G is called vertex-transitive [ 12 ] if, for any pair of vertices, there exists an automorphism of G that maps one vertex to the other. In simpler terms, the structure of the graph looks the same from every vertex. These graphs are highly symmetric- for example, the complete graph K_{n} , the cycle graph C_{n} , and the Petersen graph. 3 A combinatorial formula for \gamma(G) In this section, we study the combinatorial significance of the quantity \gamma(G) . We begin by showing that \gamma(G) characterizes the connectedness of a graph, as established in Theorem 3.1 . Then, in Theorem 3.2 , we prove that for vertex-transitive graphs, \gamma(G) admits a neat combinatorial formula in terms of the transmission of vertices. Using this result, we derive a general formula for \gamma(G) for arbitrary graphs, presented in Theorem 3.3 . This formula yields a polynomial-time algorithm for computing \gamma(G) based on the transmission values of the vertices of G . Furthermore, in Theorem 3.4 , we show that for trees, it suffices to compute the transmission of the pendant vertices to determine \gamma(G) . We need the following notation to state the first main result of this section. Let \mathcal{F}=\biggl\{x\in\mathbb{R}^{n}:\sum_{v\in V(G)}x_{v}=0~\mbox{and}~\|x\|_{\infty}=1\biggl\}. For a given x\in\mathcal{F} , define \gamma_{x}(G)=\max_{uv\in E(G)}|x_{u}-x_{v}|. In this notation, we have \gamma(G)=\min_{x\in\mathcal{F}}\gamma_{x}(G). A vector x\in\mathcal{F} is called an l_{\infty} - Fiedler vector of G if \gamma(G)=\gamma_{x}(G). Theorem 3.1 . Let G be a graph. Then G is disconnected if and only if \gamma(G)=0 . Proof. Let G be a disconnected graph having two components C_{1} and C_{2} . Without loss of generality, let |C_{1}|\leq|C_{2}| . Consider the vector x x_{v}=\left\{\begin{array}[]{ll}1&\mbox{if }v\in V(C_{1}),\\ -\frac{|C_{1}|}{|C_{2}|}&\mbox{if }v\in V(C_{2}).\end{array}\right. Then, it is easy to see that x\in\mathcal{F} and \gamma_{x}(G)=0 . So \gamma(G)=0 . Conversely, let G be a graph with \gamma(G)=0 . Let x be an l_{\infty} - Fiedler vector . Then \gamma_{x}(G)=0 , which implies that x_{u}=x_{v} whenever uv\in E(G) . If G is connected, then the vector x should be a multiple of the all-ones vector. However, this contradicts the assumption that x\in\mathcal{F} . Thus \gamma(G)\neq 0. ∎ In the next result, for the vertex-transitive graphs, we establish a relationship between the transmission of the vertices and the quantity \gamma(G) . Theorem 3.2 . Let G be a vertex-transitive connected graph with n vertices. Let u\in V(G) . Then \gamma(G)=\frac{n}{\tr(u)}. Proof. Let \diam(G)=d . Since the graph G is vertex-transitive, for every u\in V(G) , we have |S_{r}(u)|=a_{r} for 1\leq r\leq d . Then, \tr(u)=\sum^{d}_{r=1}ra_{r} for every u . Define \alpha=\frac{n}{\tr(u)} . Suppose that, there exists a vector x\in\mathcal{F} such that \gamma_{x}(G)<\alpha . Without loss of generality, let v\in V(G) be such that x_{v}=1 . If v_{r}\in S_{r}(v) , then, it is easy to see that, x_{v_{r}}>1-r\alpha for 1\leq r\leq d . But \sum_{u\in V}x_{u}>1+\sum^{d}_{r=1}a_{r}(1-r\alpha)=n-\alpha\sum^{d}_{r=1}ra_{r}=0, which is a contradiction. Hence \gamma(G)\geq\alpha . Let w be any vertex of G . Define the vector y as follows: y_{u}=\left\{\begin{array}[]{ll}1&\mbox{if }u=w,\\ 1-\alpha r&\mbox{if }u\in S_{r}(w),\end{array}\right. for 1\leq r\leq d . Then, it is easy to see that \gamma_{y}(G)=\alpha=\frac{n}{\tr(w)}. Thus, \gamma(G)=\frac{n}{\tr(w)}. ∎ Using the above theorem, we next compute \gamma(G) for the complete graphs and the cycles. This result will be used later. Corollary 3.1 . (a) Let K_{n} denote the complete graph on n vertices. Then, \gamma(K_{n})=\frac{n}{n-1} . (b) Let C_{n} denote the cycle graph on n vertices. Then, \gamma(C_{n})=\frac{n}{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil} . Proof. (a) Since \diam(K_{n})=1 and \tr(u)=n-1 for every u\in V(K_{n}) , we get \gamma(K_{n})=\frac{n}{n-1} . (b) Let n=2l for some l\in\mathbb{N} and l\geq 2 . Then, \diam(C_{2l})=l . Here a_{1}=a_{2}=\dots=a_{l-1}=2 , a_{l}=1 . Thus, \tr(u)=2\sum^{l-1}_{r=1}r+l=l^{2} for every u\in V(C_{2l}) . Hence \gamma(C_{2l})=\frac{2l}{l^{2}}=\frac{2}{l} . Let n=2l+1 for some l\in\mathbb{N} and l\geq 1 . Then, \tr(u)=2\sum^{l}_{r=1}r=l(l+1) for every u\in V(C_{2l+1}) . Hence \gamma(C_{2l+1})=\frac{2l+1}{l(l+1)} . Therefore, combining the results for even and odd values of n , we obtain \gamma(C_{n})=\frac{n}{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil} . ∎ Let u,v\in V(G) . We call u and v are equivalent vertices if there exists an automorphism \phi of G such that \phi(u)=v . The relation defined above is an equivalence relation, which partitions the vertices into equivalence classes. Let these equivalence classes be denoted by C_{1},C_{2},\dots,C_{k} . It is straightforward to verify that if u and v are equivalent , then \tr(u)=\tr(v) . Let \mathcal{D}_{M}(G) denote the maximum row sum of D(G) . Next, we prove the main result of this section. Theorem 3.3 . Let G be a connected graph on n vertices. Then \gamma(G)=\frac{n}{\max\limits_{u\in V(G)}\tr(u)}=\frac{n}{\mathcal{D}_{M}(G)}. Proof. Let C_{1},C_{2},\dots,C_{k} be the equivalence classes of vertices of G defined as above. Now, choose a vertex u_{1} from C_{1} . By following a similar argument as in Theorem 3.2 we can show that \min\{\gamma_{x}(G):x_{u_{1}}=1\}=\frac{n}{\tr(u_{1})}=\alpha_{1}\text{(say)}. Moreover, observe that if we take any vertex v_{1}\in C_{1} , then \min\{\gamma_{x}(G):x_{v_{1}}=1\}=\frac{n}{\tr(v_{1})}=\frac{n}{\tr(u_{1})}=\alpha_{1}, since u_{1} and v_{1} are equivalent vertices. Now, we can apply the same procedure to the remaining equivalence classes C_{2},\dots,C_{k} and obtain \alpha_{2},\dots,\alpha_{k} , respectively. An l_{\infty} -Fiedler vector of G should have at least one coordinate 1 . Thus, we have \gamma(G)=\min\{\alpha_{1},\alpha_{2},\dots,\alpha_{k}\}=\min_{u\in V(G)}\frac{n}{\tr(u)}=\frac{n}{\max\limits_{u\in V(G)}\tr(u)}=\frac{n}{\mathcal{D}_{M}(G)}. ∎ As a consequence of the above theorem, we present the following algorithm (in pseudocode) to compute the quantity \gamma(G) for any arbitrary connected graph G . Algorithm 1 Algorithm to compute \gamma(G) Input: A connected graph G on n vertices Output: \gamma(G) 1: maxTransmission:=0 2: for each vertex v_{i} in V(G) do 3: for each vertex v_{j} in V(G) do 4: Compute d(v_{i},v_{j}) 5: \tr(v_{i}):=\sum\limits_{j\neq i}d(v_{i},v_{j}) 6: if \tr(v_{i})>maxTransmission then 7: maxTransmission:=\tr(v_{i}) 8: return (\frac{n}{maxTransmission}) Remark 3.1 . Since the distance between any two vertices in a connected graph can be computed in polynomial time, it follows that, by using the above algorithm \gamma(G) can also be computed in polynomial time using the BFS technique. In the following remark, we provide an explicit expression for the l_{\infty} -Fiedler vector in terms of \gamma(G) . Remark 3.2 . Let G be a connected graph and u\in V(G) such that \tr(u)=\mathcal{D}_{M}(G) . Then an l_{\infty} -Fiedler vector of G is given by x_{v}=\begin{cases}1,&\text{if }v=u,\\ 1-r\gamma(G),&\text{if }v\in S_{r}(u).\end{cases} We next apply the formula given in Theorem 3.3 to determine \gamma(G) for some well-known graph families. Corollary 3.2 . (a) Let S_{n} denote the star graph on n vertices. Then \gamma(S_{n})=\frac{n}{2n-3}. (b) Let K_{m,n} denote the complete bipartite graph where the partite sets have sizes m and n with m\geq n . Then \gamma(K_{m,n})=\frac{m+n}{2m+n-2} . Proof. (a) Let u be the center vertex of S_{n} . Then \tr(u)=n-1 . If v is a pendant vertex, then \tr(v)=2n-3 . So, \mathcal{D}_{M}(S_{n})=2n-3 . Thus \gamma(S_{n})=\frac{n}{2n-3}. (b) Let (V_{1},V_{2}) be the bipartition of K_{m,n} with |V_{1}|=m and |V_{2}|=n . Then, for any vertex u\in V_{1} , \tr(u)=n+2m-2 . Similarly, for any vertex v\in V_{2} , \tr(v)=m+2n-2 . since m\geq n , \mathcal{D}_{M}(K_{m,n})=2m+n-2 . Hence follows. ∎ For trees, we make the interesting observation that the maximum transmission occurs only at the pendant vertices. Therefore, to compute \gamma(T) for a tree T , it suffices to consider only the transmissions at the pendant vertices. Theorem 3.4 . Let T be a tree, and let u\in V(T) be such that \tr(u)=\mathcal{D}_{M}(T) . Then u is a pendant vertex. Proof. Let u\in V(T) be such that \tr(u)=\mathcal{D}_{M}(T) . Suppose that the vertex u is not a pendant vertex. Let \deg u\geq 2 , and let v and w be two neighbours of u . Let S_{v} and S_{w} be the two branches rooted at u containing the vertices v and w , respectively. Without loss of generality, assume that |S_{v}|\geq|S_{w}| . Let p\in V(T) and q\in V(T) belong to the branches S_{v} and S_{w} , respectively. Then d(w,p)=d(u,p)+1 and d(w,q)=d(u,q)-1 . Thus, \tr(w)-\tr(u)\geq|S_{v}|-|S_{w}|+1>0 which is not possible, since \tr(u) is maximum. Thus, u must be a pendant vertex. ∎ Using Theorems 3.3 and 3.4 , one can directly obtain the value of \gamma(P_{n}) , which was detailed in [ 1 ] . Corollary 3.3 . Let P_{n} denote the path graph on n vertices. Then \gamma(P_{n})=\frac{2}{n-1} . Proof. Every pendant vertex of P_{n} has transmission \frac{n(n-1)}{2} . Thus \gamma(P_{n})=\frac{2}{n-1} . ∎ 4 Comparison with other parameters In this section, we compare the parameter \gamma(G) with other well-known graph invariants, such as the spectral radius of the distance matrix, the Wiener index, algebraic connectivity, b(G) , and the Cheeger’s constant. For a connected graph G , let \partial_{1}(G) denote the spectral radius of the associated distance matrix D(G) of G . Let \mathcal{D}_{M}(G) denote the maximum row sum of the distance matrix D(G) of G . Theorem 4.1 . Let G be a connected graph on n vertices. Then \gamma(G)\leq\frac{n}{\partial_{1}(G)}, where the equality holds if and only if G is a transmission-regular graph. Proof. Since the largest eigenvalue of a nonnegative matrix is bounded above by the maximum row sum [ 9 ] , the inequality follows from Theorem 3.3 . Suppose G is a transmission-regular graph. Then for every vertex u in G , we have \tr(u)=k for some k\in\mathbb{N} . This implies that all row sums of the distance matrix D(G) are equal to k , so the all-ones vector is an eigenvector of D(G) corresponding to the eigenvalue k . Since the largest eigenvalue is bounded above by k , k should be the largest eigenvalue. Thus k=\mathcal{D}_{M}(G)=\partial_{1}(G) . Conversely, assume that \mathcal{D}_{M}(G)=\partial_{1}(G) . By Perron-Frobenius theorem, let z be a positive eigenvector corresponding to the eigenvalue \partial_{1}(G) . Let z_{k}=\max\limits_{i\in V(G)}z_{i} . Then for the k -th row in D(G) , we have \partial_{1}(G)z_{k}=\sum\limits_{j=1}^{n}D_{kj}z_{j}\leq z_{k}(\sum\limits_{j=1}^{n}D_{kj}). Hence \partial_{1}(G)\leq\sum\limits_{j=1}^{n}D_{kj} . Since \mathcal{D}_{M}(G)=\partial_{1}(G) , we have \partial_{1}(G)=\sum\limits_{j=1}^{n}D_{kj} . Thus z_{j}=z_{k} for all j\in\{1,2,\dots,n\} . Hence, the all-ones vector is an eigenvector corresponding to the eigenvalue \partial_{1} , that is, all the row sums of \mathcal{D}_{M}(G) are equal. So, G is a transmission-regular graph. ∎ Remark 4.1 . A number of lower bounds for \partial_{1}(G) have been extensively studied in the literature [ 2 ] . These findings can be used to derive further upper bounds for \gamma(G) across various classes of graphs. The Wiener index W(G) of a graph G is the sum of distances between all unordered pairs of vertices of G [ 2 ] . Note that the Wiener index W(G) of a graph G is half of the sum of transmissions of all the vertices of G . W(G)=\frac{\sum\limits_{u\in V(G)}\tr(u)}{2}. In the next theorem, we establish a relationship between \gamma(G) and the Wiener index of the graph G . Theorem 4.2 . Let G be a connected graph on n vertices. Then \gamma(G)\leq\frac{n^{2}}{2W(G)}. Furthermore, equality holds if and only if G is a transmission-regular graph. Proof. Note that \displaystyle W(G) \displaystyle=\frac{\sum\limits_{u\in V(G)}\tr(u)}{2} \displaystyle\leq\frac{n}{2}\max\limits_{u\in V(G)}\tr(u). That is, \max\limits_{u\in V(G)}\tr(u)\geq\frac{2W(G)}{n} . The result now follows directly from Theorem 3.3 . The equality holds if and only if all vertex transmissions are equal; that is, G is a transmission-regular graph. ∎ Next, we provide a bound for b(G) in terms of \gamma(G) . Theorem 4.3 . Let G be a graph with m edges. Then b(G)\leq\frac{m}{2}\gamma(G) . Proof. Let x be an l_{\infty} -Fiedler vector of G . Let u\in V(G) be such that x_{u}=1 . Then \|x\|_{1}=1+\sum_{\begin{subarray}{c}v\neq u\\ v\in V(G)\end{subarray}}|x_{v}|\geq 1+|\sum_{\begin{subarray}{c}v\neq u\\ v\in V(G)\end{subarray}}x_{v}|=2. Now, define x^{*}=\frac{x}{\|x\|_{1}} . Then \|x^{*}\|_{1}=1 . As \sum\limits_{v\in V(G)}x_{v}=0 , so \sum\limits_{v\in V(G)}x^{*}_{v}=0 . Therefore, \displaystyle b(G) \displaystyle=\min\biggl\{\sum_{uv\in E(G)}|y_{u}-y_{v}|:\sum_{v\in V(G)}y_{v}=0~\mbox{{and}~}\|y\|_{1}=1\biggl\} \displaystyle\leq\sum\limits_{uv\in E(G)}|x^{*}_{u}-x^{*}_{v}| \displaystyle=\frac{1}{\|x\|_{1}}\sum_{uv\in E(G)}|x_{u}-x_{v}| \displaystyle\leq\frac{1}{2}\sum_{uv\in E(G)}|x_{u}-x_{v}| \displaystyle\leq\frac{m}{2}\gamma(G). ∎ This lemma will be useful in the proof of the next theorem. Lemma 4.1 . Let G be a connected graph with n vertices. Let x be an l_{\infty} -Fiedler vector of G . Then \|x\|^{2}_{2}\geq\frac{n}{n-1} . Equality holds if and only if G is isomorphic to the complete graph K_{n} . Proof. Let u\in V(G) such that x_{u}=1 . By applying the Cauchy-Schwarz inequality, we obtain (\sum_{v\neq u}x_{v})^{2}\leq(\sum_{v\neq u}1^{2})(\sum_{v\neq u}x_{v}^{2}). Therefore, we have \sum\limits_{v\neq u}x_{v}^{2}\geq\frac{1}{n-1} . Hence \|x\|^{2}_{2}\geq\frac{n}{n-1} . The equality holds if and only if x_{v}=-\frac{1}{n-1} for all v\neq u . In this case, \gamma(G)=\gamma_{x}(G)=\frac{n}{n-1} . Then, by Theorem 3.3 , we have \max\limits_{v\in V(G)}\tr(v)=n-1 . Since \tr(v)\geq n-1 for every v\in V(G) , we have \tr(v)=n-1 for all v\in V(G) . Hence, G is isomorphic to K_{n} . ∎ Using the bound on the norm of l_{\infty} -Fiedler vector derived above, we now establish a relation between \gamma(G) and the algebraic connectivity a(G) . Theorem 4.4 . Let G be a connected graph with n vertices and m edges. Then a(G)<\frac{m(n-1)}{n}\gamma(G)^{2} . Proof. If G=K_{n} , we have a(K_{n})=n [ 6 ] . We know \gamma(K_{n})=\frac{n}{n-1} . Hence, for n\geq 2 , we have a(K_{n})=n<\frac{n^{2}}{2}=\frac{m(n-1)}{n}\gamma(K_{n})^{2} . Let G\neq K_{n} . Let x be an l_{\infty} -Fiedler vector of G . Observe that, if vw\in E(G) , then |x_{v}-x_{w}|\leq\gamma(G) . Now, by the variational characterization of the second smallest eigenvalue [ 9 ] , we have \displaystyle a(G) \displaystyle\leq\frac{x^{T}L(G)x}{x^{T}x} \displaystyle=\frac{\sum\limits_{vw\in E(G)}(x_{v}-x_{w})^{2}}{||x||^{2}_{2}} \displaystyle<\frac{m(n-1)}{n}\gamma(G)^{2}, where the last inequality follows from Lemma 4.1 . ∎ Let S\subseteq V(G) . The volume of S , denoted by \vol(S) , is the sum of the degrees of all vertices in S , that is \vol(S)=\sum\limits_{u\in S}\deg(u). For a proper subset S\subsetneq V(G) , the boundary of S , denoted by \partial S , is the set of all edges with exactly one endpoint in S . Formally \partial S=\biggl\{uv\in E(G):u\in S~\mbox{and}~v\in S^{c}\biggl\}. The following definitions and results are from [ 5 ] . For a subset S\subsetneq V(G) , h_{G}(S) is defined as: h_{G}(S)=\frac{|\partial S|}{\min(\vol(S),\vol(S^{c}))}. The Cheeger constant h_{G} of a graph G is given by h_{G}=\min\limits_{S\subsetneq V(G)}h_{G}(S). Let G be a graph on n vertices. Then the normalized Laplacian of G , denoted by \mathcal{L}(G) , is given by \mathcal{L}_{uv}(G)=\begin{cases}1&\text{if }u=v\text{ and }\deg(v)\neq 0,\\ -\dfrac{1}{\sqrt{\deg(u)\deg(v)}}&\text{if u and v are adjacent},\\ 0&\text{otherwise}.\end{cases} In [ 5 ] , the author defined \mathcal{L}(G) to be the Laplacian matrix associated with the graph G . If G is connected graph, then we have \mathcal{L}(G)=\Delta(G)^{\frac{-1}{2}}L(G)\Delta(G)^{\frac{-1}{2}} . The spectrum of \mathcal{L}(G) is denoted by \{\mu_{1}(G),\mu_{2}(G),\dots,\mu_{n}(G)\} , where the eigenvalues are arranged in non-increasing order: \mu_{1}(G)\geq\mu_{2}(G)\geq\dots\geq\mu_{n}(G) . The Cheeger inequality is given by 2h_{G}\geq\mu_{n-1}(G)>\frac{h_{G}^{2}}{2}. Theorem 4.5 . Let G be a connected k -regular graph on n vertices. Then h_{G}<\sqrt{n-1}\gamma(G) . Proof. Let G be k -regular graph. Then \mathcal{L}(G)=\frac{1}{k}L(G) and \mu_{n-1}(G)=\frac{a(G)}{k} . Since |E(G)|=\frac{kn}{2} , from Theorem 4.4 , we have \mu_{n-1}(G)<\frac{n-1}{2}\gamma(G)^{2} . The result follows from the Cheeger inequality. ∎ Note that if H is a graph obtained by adding an edge to the graph G , then \gamma(H)\geq\gamma(G) . To see this, let x\in\mathcal{F} . Then \gamma_{x}(H)\geq\gamma_{x}(G) . Taking the minimum over all x\in\mathcal{F} on both sides yields the desired inequality. Next, we establish bounds on the quantity \gamma(G) in terms of the number of vertices and provide a complete characterization of the extremal graphs. Theorem 4.6 . Let G be a connected graph on n vertices. Then \frac{2}{n-1}\leq\gamma(G)\leq\frac{n}{n-1}. Furthermore, equality holds on the left-hand side if and only if G is isomorphic to P_{n} , and equality holds on the right-hand side if and only if G is isomorphic to K_{n} . Proof. If H is a spanning subgraph of a graph G , then \gamma(H)\leq\gamma(G) . Thus \gamma(G)\leq\gamma(K_{n})=\frac{n}{n-1}. The upper bound is attained if and only if \max\limits_{u\in V(G)}\tr(u)=n-1 . Since \tr(u)\geq n-1 for every u\in V(G) , this implies that \tr(u)=n-1 for all u\in V(G) . Hence, G=K_{n} . Note that for any vertex u\in V(G) , \tr(u)\leq\frac{n(n-1)}{2}. Thus, \max\limits_{u\in V(G)}\tr(u)\leq\frac{n(n-1)}{2}, which implies \gamma(G)\geq\frac{2}{n-1}. For equality to hold, the diameter of the graph G should be n-1 . Hence, P_{n} is the only graph that attains the lower bound. ∎ Theorem 4.7 . Let T be a tree on n(\geq 3) vertices. Then \frac{2}{n-1}\leq\gamma(T)\leq\frac{n}{2n-3}. Furthermore, equality holds on the left-hand side if and only if G is isomorphic to P_{n} , and equality holds on the right-hand side if and only if G is isomorphic to S_{n} . Proof. The left-hand side of the inequality follows from Theorem 4.6 . By Corollary (a) , we have \mathcal{D}_{M}(S_{n})=2n-3 . We now show that for any tree on n vertices, \mathcal{D}_{M}(T)\geq 2n-3 . Let u\in V(T) be such that \tr(u)=\mathcal{D}_{M}(T) . Then, by Theorem 3.4 , the vertex u should be a pendant vertex. So, the vertex u has exactly one neighbor, and the other vertices of T are at a distance of at least 2 from u . Hence \mathcal{D}_{M}(T)=\tr(u)\geq 2n-3. This gives the upper bound: \gamma(T)\leq\frac{n}{2n-3}. To get equality in the above expression, we must have the diameter of the tree T equal to 2 . It is easy to verify that the star graph S_{n} is the unique tree with diameter 2 . Hence, the extremal graph is unique. ∎ 5 Cartesian product In this section, we derive a formula for \gamma(G) when G is the Cartesian product of some finite families of graphs, expressing it in terms of the corresponding values for their constituent graphs. As a by-product of this formula, we obtain explicit values of \gamma(G) for several well-known families of graphs. The Cartesian product of two graphs G and H , denoted by G\times H , is the graph with the vertex set V(G)\times V(H) , and edges defined as follows: (u_{1},v_{1})\sim(u_{2},v_{2}) if either u_{1}\sim u_{2} in G and v_{1}=v_{2} , or u_{1}=u_{2} and v_{1}\sim v_{2} in H [ 8 ] . Theorem 5.1 . Let G and H be two connected graphs. Then \gamma(G\times H)=\frac{1}{\frac{1}{\gamma(G)}+\frac{1}{\gamma(H)}}. Proof. Let G and H be graphs of order n and m , respectively. Let \mathcal{D}_{M}(G)=t_{1} , \mathcal{D}_{M}(H)=t_{2} . Then \gamma(G)=n/t_{1} and \gamma(H)=m/t_{2} . For any two vertices (u_{1},v_{1}) and (u_{2},v_{2}) in G\times H , it is easy to see that d_{G\times H}\{(u_{1},v_{1}),(u_{2},v_{2})\}=d_{G}(u_{1},u_{2})+d_{H}(v_{1},v_{2}). So, the transmission of a vertex (u,v) in G\times H is given by \displaystyle\tr_{G\times H}(u,v) \displaystyle=\sum\limits_{(u^{\prime},v^{\prime})\in V(G\times H)}(d_{G}(u,u^{\prime})+d_{H}(v,v^{\prime})) \displaystyle=\sum\limits_{(u^{\prime},v^{\prime})\in V(G\times H)}d_{G}(u,u^{\prime})+\sum\limits_{(u^{\prime},v^{\prime})\in V(G\times H)}d_{H}(v,v^{\prime}) \displaystyle=m\sum\limits_{u^{\prime}\in V(G)}d_{G}(u,u^{\prime})+n\sum\limits_{v^{\prime}\in V(H)}d_{H}(v,v^{\prime}) \displaystyle=m\tr_{G}(u)+n\tr_{H}(v). To maximize this over all (u,v)\in V(G\times H) , we pick u\in V(G) with transmission t_{1} and v\in V(G) with transmission t_{2} . Hence, \mathcal{D}_{M}(G\times H)=mt_{1}+nt_{2} . Therefore, by Theorem 3.3 , \gamma(G\times H)=\frac{mn}{mt_{1}+nt_{2}}=\frac{1}{\frac{t_{1}}{n}+\frac{t_{2}}{m}}=\frac{1}{\frac{1}{\gamma(G)}+\frac{1}{\gamma(H)}}. ∎ Similarly, the Cartesian product of the graphs G_{1},G_{2},\dots,G_{k} , denoted by G_{1}\times G_{2}\times\dots\times G_{k} , is the graph with the vertex set V(G_{1})\times V(G_{2})\times\dots\times V(G_{k}) , and the edge set defined as follows: (u_{1},u_{2},\dots,u_{k})\sim(v_{1},v_{2},\dots,v_{k}) if there exists exactly one index i\in\{1,2,\dots,k\} such that u_{i}\sim v_{i} in G_{i} , and u_{j}=v_{j} for all j\neq i . Building on the proof of the above theorem, we can extend the argument to establish the following result for a finite Cartesian product of graphs. Theorem 5.2 . Let G_{1},G_{2},\dots,G_{k} be a collection of connected graphs. Then \gamma(G_{1}\times G_{2}\times\dots\times G_{k})=\frac{1}{\frac{1}{\gamma(G_{1})}+\frac{1}{\gamma(G_{2})}+\dots+\frac{1}{\gamma(G_{k})}}. Using the above theorem, we can compute the explicit value of \gamma(G) for several well-known families of graphs. We present a few of them here. (a) The t -dimensional hypercube Q_{t} is the Cartesian product of t -copies of the complete graph K_{2} . Since \gamma(K_{2})=2 , we have \gamma(Q_{t})=\frac{2}{t} . (b) The Hamming graph H(t,s) is the Cartesian product of t -copies of the complete graph K_{s} . Hence \gamma(H(t,s))=\frac{s}{t(s-1)}. (c) The grid graph G_{l,m,n} is the Cartesian product of paths P_{l} , P_{m} and P_{n} . Now, by Theorem 4.6 , we obtain \gamma(G_{l,m,n})=\frac{2}{l+m+n-3} . (d) The torus grid graph T_{m,n} is the Cartesian product of two cycle graphs C_{m} and C_{n} . By Corollary 3.1 , we have \gamma(C_{n})=\frac{n}{\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil} . Thus \gamma(T_{m.n})=\frac{mn}{m\lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil+n\lfloor\frac{m}{2}\rfloor\lceil\frac{m}{2}\rceil}. 6 Conclusion In this work, we studied the parameter \gamma(G) as an l_{\infty} -analogue of the classical algebraic connectivity and demonstrated that \gamma(G) characterizes the connectedness of the underlying graph G . We established a combinatorial formula for \gamma(G) based on the maximum row sum of the distance matrix of G , which enables efficient computation of \gamma(G) using a breadth-first search algorithm. Additionally, we explored the relationship between \gamma(G) and several other graph parameters. Furthermore, we derived a formula for \gamma(G) when G is the Cartesian product of finitely many graphs, and calculated \gamma(G) for some well-known graphs. Graph smoothing with respect to the l_{2} -norm is well-studied, while the corresponding problems for the l_{1} -norm and the l_{\infty} -norm were introduced by Andrade and Dahl [ 1 ] . In this paper, we further investigate the graph smoothing problem for the l_{\infty} -norm. We conclude with the following table summarizing the graph smoothing problems with respect to the l_{2} -norm, l_{1} -norm, and l_{\infty} -norm. The conclusions in the last column are based on the results presented in this work. Name l_{2} -graph smoothing l_{1} -graph smoothing l_{\infty} -graph smoothing Problem \min\limits_{x}\sum\limits_{uv\in E(G)}(x_{u}-x_{v})^{2} \min\limits_{x}\sum\limits_{uv\in E(G)}\lvert x_{u}-x_{v}\rvert \min\limits_{x}\max\limits_{uv\in E(G)}\lvert x_{u}-x_{v}\rvert subject to \|x\|_{2}=1 , x\perp e subject to \|x\|_{1}=1 , x\perp e subject to \|x\|_{\infty}=1 , x\perp e Solution a(G) b(G) \gamma(G) Encodes Yes Yes Yes the connectedness Relevance partition Sparsest cut max transmission Strategy spectral combinatorial combinatorial (NP-hard) (Polynomial-time) Table 1: Comparison of graph smoothing problems under different norms.