Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
In this paper, using matrix techniques, we compute the Ihara-zeta function and the number of spanning trees of the join of two semi-regular bipartite graphs. Furthermore, we show that the spectrum and the zeta function of the join of two semi-regular bipartite graphs can determine each other.
A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s geq 3$ and $t geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $Theta ( n^{t/2})$. More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s geq 4$ and $t geq 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $Omega( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.
A graph $G$ contains $H$ as an emph{immersion} if there is an injective mapping $phi: V(H)rightarrow V(G)$ such that for each edge $uvin E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $phi(u)$ and $phi(v)$, and all the paths $P_{uv}$, $uvin E(H)$, are pairwise edge-disjoint. An analogue of Hadwigers conjecture for the clique immersions by Lescure and Meyniel states that every graph $G$ contains $K_{chi(G)}$ as an immersion. We consider the average degree condition and prove that for any bipartite graph $H$, every $H$-free graph $G$ with average degree $d$ contains a clique immersion of order $(1-o(1))d$, implying that Lescure and Meyniels conjecture holds asymptotically for graphs without fixed bipartite graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
