A partial proof of the Brouwer’s conjecture

Slobodan Filipovski · 2024

Read A partial proof of the Brouwer’s conjecture by Slobodan Filipovski (2024) 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-2412-12952.txt.

Introduction

Slobodan Filipovski gives a partial proof of Brouwer's conjecture in two thousand twenty-four. The conjecture caps sums of top Laplacian eigenvalues of a graph. The cap blends edge count with a binomial term in the count taken. He proves the bound for two ranges of graphs and indices. One range ties edge and vertex counts by a square root law. The other sets the index in a band built from those counts. Both bands are wide but not the full claim.

Catalog record

CREATORSlobodan Filipovski
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-12952

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A partial proof of the Brouwer’s conjecture Slobodan Filipovski Abstract Let G G be a simple graph with n n vertices and m m edges and let k k be a natural number such that k ≤ n . k\leq n. Brouwer conjectured that the sum of the k k largest Laplacian eigenvalues of G G is at most m + ( k + 1 2 ) . m+{k+1\choose 2}. In this paper we prove that this conjecture is true for simple ( m , n ) (m,n) -graphs where n ≤ m ≤ 3 − 1 4 ​ ( n − 1 ) ​ n n\leq m\leq\frac{\sqrt{3}-1}{4}(n-1)n and k ∈ [ 8 ​ m 2 n − 1 + 4 ​ m ​ n + n 2 3 , n ] . k\in\left[\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}},n\right]. Moreover, we prove that the conjecture is true for all simple ( m , n ) (m,n) -graphs where k ( ≤ n ) k(\leq n) is a natural number from the interval [ 2 ​ n − 2 ​ m + 2 ​ 2 ​ m 2 + m ​ n ​ ( n − 1 ) , 1 + 8 ​ m 2 n 2 ​ ( n − 1 ) + 4 ​ m n ] . \left[\sqrt{2n-2m+2\sqrt{2m^{2}+mn(n-1)}},1+\frac{8m^{2}}{n^{2}(n-1)}+\frac{4m}{n}\right]. 1 Introduction Let G be a simple graph with vertex set V(G) and edge set E(G) and let |V(G)|=n and |E(G)|=m. The degree of a vertex v\in V(G) denoted by d(v) , is the number of neighbours of v . The Laplacian matrix of G is the n\times n matrix L(G)=[l_{ij}] defined as L(G)=D(G)-A(G) , where D(G) is the diagonal matrix of vertex degrees of the graph G , and A(G) is the adjacency matrix of G . It is well known that L(G) is a positive semidefinite matrix, consequently its eigenvalues are nonnegative real numbers. The eigenvalues of L(G) are called the Laplacian eigenvalues of G and are denoted by \mu_{1}(G)\geq\mu_{2}(G)\geq\ldots\geq\mu_{n}(G) . Since each row sum of L(G) is 0 , it holds \mu_{n}(G)=0. In this paper, we study the sum S_{k}(G)=\sum_{i=1}^{k}\mu_{i}(G) for 1\leq k\leq n . Brouwer [ 1 ] has conjectured the following upper bound for the sum S_{k}(G). Conjecture 1 . [ 1 ] Let G be a graph with vertices n and edges m . Then S_{k}(G)\leq m+{k+1\choose 2} for k=1,2,\ldots,n. Based on a computer check, Brouwer [ 1 ] showed that the Conjecture 1 is true for all graphs with at most 10 vertices. There have been many partial proofs of this conjecture using specific methods from spectral graph theory. For k=1 , the conjecture follows from the well-known inequality \mu_{1}(G)\leq|V(G)|=n, see in [ 7 ] . The conjecture has been proved to be true for any graphs with k=2,n-2,n-3 , see [ 5 , 8 ] , trees [ 8 ] , threshold graphs [ 9 ] , unicyclic graphs [ 6 ] , bicyclic graphs [ 6 , 12 ] , tricyclic graphs having no pendant vertices [ 10 , 12 ] , regular graphs [ 2 , 11 ] , split graphs [ 11 ] , cographs [ 2 , 11 ] , planar graphs when k\geq 11 and bipartite graphs when k\geq\sqrt{32n} [ 4 ] . Also the cases k=n and k=n-1 are straightforward. Another related upper bound was given by Zhou in [ 14 ] : S_{k}(G)\leq\frac{2mk+\sqrt{mk(n-k-1)(n^{2}-n-2m)}}{n-1} where 1\leq k\leq n-2 and m=|E(G)|. In this paper we prove that the Brouwer’s conjecture is true for all simple (m,n) -graphs where n\leq m\leq\frac{\sqrt{3}-1}{4}(n-1)n and k\in\left[\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}},n\right]. Moreover, we prove that this conjecture is true for all simple (m,n) -graphs where k\leq n is a natural number from the interval \left[\sqrt{2n-2m+2\sqrt{2m^{2}+mn(n-1)}},1+\frac{8m^{2}}{n^{2}(n-1)}+\frac{4m}{n}\right]. 2 A partial proof of the conjecture Let J be all-ones matrix of size n and let L^{{}^{\prime}}=J-L. Since (L^{{}^{\prime}})^{\texttt{T}}=J^{\texttt{T}}-L^{\texttt{T}}=J-L=L^{{}^{\prime}}, we obtain that L^{{}^{\prime}} is a symmetric matrix. Let \mu_{1}\geq\mu_{2}\geq\ldots\geq\mu_{n} be the eigenvalues of L , and let \mu_{1}^{{}^{\prime}}\geq\mu_{2}^{{}^{\prime}}\geq\ldots\geq\mu_{n}^{{}^{\prime}} be the eigenvalues of L^{{}^{\prime}}, in the decreasing order. Moreover, let \lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n} be the eigenvalues of J . It is well-known that \lambda_{1}(J)=n and \lambda_{i}(J)=0 , for i=2,3,\ldots,n. Applying the Weyl’s inequality [ 13 ] we get the following result. Lemma 2 . a) \mu_{i}+\mu^{{}^{\prime}}_{n-i+2}\leq 0\;\;\text{for}\;\;i=2,3,\ldots,n. b) \mu_{1}+\mu_{1}^{{}^{\prime}}\geq n. Proof. a) From Weyl’s inequality we get: \mu_{i}(L)+\mu^{{}^{\prime}}_{j}(L^{{}^{\prime}})\leq\lambda_{i+j-n}(L+L^{{}^{\prime}})=\lambda_{i+j-n}(J). (1) Setting j=n-i+2 in ( 1 ) we get the inequality: \mu_{i}+\mu^{{}^{\prime}}_{n-i+2}\leq\lambda_{2}(J)=0,\;\;\text{for}\;\;i=2,3,\ldots,n. (2) b) Since \text{trace}(L)=\sum_{i=1}^{n}\mu_{i}, \text{trace}(L^{{}^{\prime}})=\sum_{i=1}^{n}\mu_{i}^{{}^{\prime}} and \text{trace}(L)+\text{trace}(L^{{}^{\prime}})=\text{trace}(J)=n we have \mu_{1}+\mu_{1}^{{}^{\prime}}+\sum_{i=2}^{n}(\mu_{i}+\mu_{n-i+2}^{{}^{\prime}})=n. From a) we get \mu_{1}+\mu_{1}^{{}^{\prime}}\geq n. ∎ The first Zagreb index for a graph with a vertex set \{v_{1},v_{2},\ldots,v_{n}\} and vertex degrees d_{i}=\text{deg}(v_{i}) for i=1,\ldots,n is defined by M_{1}(G)=\sum_{i=1}^{n}d_{i}^{2}. The following upper bound for M_{1} , obtained by de Caen in [ 3 ] , will be used in our proof. Lemma 3 . [ 3 ] Let G=(V,E) be a graph with n vertices and m edges. Then M_{1}(G)=\sum_{i=1}^{n}d_{i}^{2}\leq\frac{2m^{2}}{n-1}+mn-2m. Moreover, if G is connected, then equality holds if and only if G is either a star K_{1,n-1} or a complete graph K_{n}. In the next theorem we give an upper bound for S_{k}(G) in terms of m,n and k. Theorem 4 . Let G be a simple graph on n vertices and m edges. Then S_{k}(G)=\sum_{i=1}^{k}\mu_{k}\leq n+\sqrt{(k-1)\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)}. Proof. From \text{trace}(L\cdot L^{\texttt{T}})=\sum_{i=1}^{n}\sum_{j=1}^{n}l_{ij}^{2} and L=L^{\texttt{T}} we obtain \sum_{i=1}^{n}\mu_{i}^{2}=\text{trace}(L^{2})=\text{trace}(L\cdot L^{\texttt{T}})=\sum_{i=1}^{n}\sum_{j=1}^{n}l_{ij}^{2}. (3) Analogously we get \sum_{i=1}^{n}(\mu_{i}^{{}^{\prime}})^{2}=\text{trace}((L^{{}^{\prime}})^{2})=\text{trace}(L^{{}^{\prime}}\cdot(L^{{}^{\prime}})^{\texttt{T}})=\sum_{i=1}^{n}\sum_{j=1}^{n}(l_{ij}^{{}^{\prime}})^{2}. (4) Combining ( 3 ) and ( 4 ) we get: \sum_{i=1}^{n}\mu_{i}^{2}+\sum_{i=1}^{n}(\mu_{i}^{{}^{\prime}})^{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}l_{ij}^{2}+\sum_{i=1}^{n}\sum_{j=1}^{n}(l_{ij}^{{}^{\prime}})^{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}(l_{ij}^{2}+(1-l_{ij})^{2}) =\sum_{i=1}^{n}\sum_{j=1}^{n}(2l_{ij}^{2}-2l_{ij}+1)=\left(\sum_{i=1}^{n}2d_{i}^{2}-\sum_{i=1}^{n}2d_{i}+n\right)+\left(\sum_{i=1}^{n}\sum_{j=1,j\neq i}^{n}(2l_{ij}^{2}-2l_{ij}+1)\right) =(2M_{1}-4m+n)+((4+4+\ldots+4)+n^{2}-n) =2M_{1}-4m+n+2m\cdot 4+n^{2}-n=2M_{1}+4m+n^{2}. Let t=\frac{\mu_{1}}{n}. Since \mu_{1}\leq n we get 0<t\leq 1. The inequality \mu_{1}+\mu_{1}^{{}^{\prime}}\geq n implies \mu_{1}^{2}+(\mu_{1}^{{}^{\prime}})^{2}\geq n^{2}t^{2}+n^{2}(1-t)^{2}=n^{2}(2t^{2}-2t+1). (5) Moreover, from \mu_{i}+\mu^{{}^{\prime}}_{n-i+2}\leq 0,\;\;\text{for}\;\;i=2,3,\ldots,n, and from \mu_{i}\geq 0 we easily conclude that \mu_{i}^{2}\leq(\mu_{n-i+2}^{{}^{\prime}})^{2}. Therefore we have 2M_{1}+4m+n^{2}=\sum_{i=1}^{n}\mu_{i}^{2}+\sum_{i=1}^{n}(\mu_{i}^{{}^{\prime}})^{2}=(\mu_{1}^{2}+(\mu_{1}^{{}^{\prime}})^{2})+\sum_{i=2}^{n}(\mu_{i}^{2}+(\mu_{n-i+2}^{{}^{\prime}})^{2}) \geq(1-2t(1-t))n^{2}+2\sum_{i=2}^{n}\mu_{i}^{2}. From the last inequality we get \sum_{i=2}^{k}\mu_{i}^{2}\leq\sum_{i=2}^{n}\mu_{i}^{2}\leq\frac{2M_{1}+4m+n^{2}}{2}-\frac{(1-2t(1-t))n^{2}}{2}. (6) Now, based on the inequality ( 6 ) and applying the inequality between the arithmetic and quadratic means for the nonnegative eigenvalues \mu_{2},\mu_{3},\ldots,\mu_{n} we get \sum_{i=2}^{k}\mu_{i}\leq\sqrt{(k-1)(\mu_{2}^{2}+\ldots+\mu_{k}^{2})}\leq\sqrt{(k-1)\left(\frac{2M_{1}+4m+n^{2}}{2}-\frac{(1-2t(1-t))n^{2}}{2}\right)}. (7) Hence we get S_{k}(G)=\sum_{i=1}^{k}\mu_{i}=\mu_{1}+\sum_{i=2}^{n}\mu_{i}\leq nt+\sqrt{(k-1)\left(M_{1}+2m+n^{2}t(1-t)\right)}. (8) Setting M_{1}\leq\frac{2m^{2}}{n-1}-2m+mn in ( 8 ) we obtain the following inequality \sum_{i=1}^{k}\mu_{i}\leq nt+\sqrt{(k-1)\left(\frac{2m^{2}}{n-1}+mn+n^{2}t(1-t)\right)}. (9) In the end, from t\leq 1 and t(1-t)\leq\frac{1}{4} we have S_{k}(G)=\sum_{i=1}^{k}\mu_{i}\leq n+\sqrt{(k-1)\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)}. ∎ Theorem 5 . Let G be a simple graph on n vertices and m edges such that n\leq m\leq\frac{\sqrt{3}-1}{4}(n-1)n. The Brouwer’s conjecture holds for all natural numbers k from the interval \left[\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}},n\right]. Proof. The bound in Theorem 4 and the assumption n\leq m yield S_{k}(G)\leq n+\sqrt{(k-1)\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)}<m+\sqrt{k\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)}. (10) Now, we are going to show that for k\in\left[\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}},n\right] , it holds m+\sqrt{k\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)}\leq m+{k+1\choose 2}. Since \frac{k^{2}}{2}<{k+1\choose 2}, it suffices to prove that k\left(\frac{2m^{2}}{n-1}+mn+\frac{n^{2}}{4}\right)\leq\frac{k^{4}}{4}, which obviously holds for k\geq\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}}. In the end, we verify that for m\leq\frac{\sqrt{3}-1}{4}(n-1)n it occurs \sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}}<n. The inequality \sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}}<n is equivalent to the quadratic inequality (in m ) 8m^{2}+4mn(n-1)-n^{2}(n-1)^{2}<0. (11) Solving the inequality ( 11 ) we get m\in\left(\frac{(-\sqrt{3}-1)}{4}n(n-1),\frac{(\sqrt{3}-1)}{4}n(n-1)\right). ∎ Remark 6 . We illustrate the above theorem for simple graphs on 100 vertices. From the condition n\leq m\leq\frac{\sqrt{3}-1}{4}n(n-1) we have 100\leq m\leq 1811. Based on the restrictions for k , that is, k\in\left[\sqrt[3]{\frac{8m^{2}}{n-1}+4mn+n^{2}},n\right], in the table below we consider particular examples and give the corresponding values of k for which the Brouwer’s conjecture is true. m k 100 [38, 100] 200 [46, 100] 300 [52, 100] 400 [57, 100] 500 [62, 100] 600 [66, 100] 700 [70, 100] Note that the Theorem 5 concerns the simple graphs with n vertices and with at

Read the complete text