Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe normalized Laplacian spectrum of subdivisions of a graph
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Determining and analyzing the spectra of graphs is an important and exciting research topic in theoretical computer science. The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some relevant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs. As an example of application of these results we find the exact values of their multiplicative degree-Kirchhoff index, Kemenys constant and number of spanning trees.
rate research
Read More
The spectrum of the normalized graph Laplacian yields a very comprehensive set of invariants of a graph. In order to understand the information contained in those invariants better, we systematically investigate the behavior of this spectrum under local and global operations like motif doubling, graph joining or splitting. The eigenvalue 1 plays a particular role, and we therefore emphasize those constructions that change its multiplicity in a controlled manner, like the iterated duplication of nodes.
We study the spectrum of the normalized Laplace operator of a connected graph $Gamma$. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose $Gamma$ into two large pieces, whereas the largest eigenvalue controls how close $Gamma$ is to being bipartite. The smallest eigenvalue can be controlled by the Cheeger constant, and we establish a dual construction that controls the largest eigenvalue. Moreover, we find that the neighborhood graphs $Gamma[l]$ of order $lgeq2$ encode important spectral information about $Gamma$ itself which we systematically explore. In particular, the neighborhood graph method leads to new estimates for the smallest nontrivial eigenvalue that can improve the Cheeger inequality, as well as an explicit estimate for the largest eigenvalue from above and below. As applications of such spectral estimates, we provide a criterion for the synchronizability of coupled map lattices, and an estimate for the convergence rate of random walks on graphs.
We obtain new bounds for the Laplacian spectral radius of a signed graph. Most of these new bounds have a dependence on edge sign, unlike previously known bounds, which only depend on the underlying structure of the graph. We then use some of these bounds to obtain new bounds for the Laplacian and signless Laplacian spectral radius of an unsigned graph by signing the edges all positive and all negative, respectively.
Brouwers Conjecture states that, for any graph $G$, the sum of the $k$ largest (combinatorial) Laplacian eigenvalues of $G$ is at most $|E(G)| + binom{k+1}{2}$, $1 leq k leq n$. We present several interrelated results establishing Brouwers conjecture $text{BC}_k(G)$ for a wide range of graphs $G$ and parameters $k$. In particular, we show that (1) $text{BC}_k(G)$ is true for low-arboricity graphs, and in particular for planar $G$ when $k geq 11$; (2) $text{BC}_k(G)$ is true whenever the variance of the degree sequence is not very high, generalizing previous results for $G$ regular or random; (3) $text{BC}_k(G)$ is true if $G$ belongs to a hereditarily spectrally-bounded class and $k$ is sufficiently large as a function of $k$, in particular $k geq sqrt{32n}$ for bipartite graphs; (4) $text{BC}_k(G)$ holds unless $G$ has edge-edit distance $< k sqrt{2n} = O(n^{3/2})$ from a split graph; (5) no $G$ violates the conjectured upper bound by more than $O(n^{5/4})$, and bipartite $G$ by no more than $O(n)$; and (6) $text{BC}_k(G)$ holds for all $k$ outside an interval of length $O(n^{3/4})$. Furthermore, we present a surprising negative result: asymptotically almost surely, a uniform random signed complete graph violates the conjectured bound by $Omega(n)$.
Bimonotone subdivisions in two dimensions are subdivisions all of whose sides are either vertical or have nonnegative slope. They correspond to statistical estimates of probability distributions of strongly positively dependent random variables. The number of bimonotone subdivisions compared to the total number of subdivisions of a point configuration provides insight into how often the random variables are positively dependent. We give recursions as well as formulas for the numbers of bimonotone and total subdivisions of $2times n$ grid configurations in the plane. Furthermore, we connect the former to the large Schroder numbers. We also show that the numbers of bimonotone and total subdivisions of a $2times n$ grid are asymptotically equal. We then provide algorithms for counting bimonotone subdivisions for any $m times n$ grid. Finally, we prove that all bimonotone triangulations of an $m times n$ grid are connected by flips. This gives rise to an algorithm for counting the number of bimonotone (and total) triangulations of an $mtimes n$ grid.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
