ﻻ يوجد ملخص باللغة العربية
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e in E(overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $ntoinfty$.
Write $rholeft( Gright) $ for the spectral radius of a graph $G$ and $S_{n,r}$ for the join $K_{r}veeoverline{K}_{n-r}.$ Let $n>rgeq2$ and $G$ be a $K_{r+1}$-saturated graph of order $n.$ Recently Kim, Kim, Kostochka, and O determined exactly the
The ErdH{o}s-Simonovits stability theorem states that for all epsilon >0 there exists alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - alpha n^2, then one can remove epsilon n^2 edges from G to obtain an r-par
Let $tgeq3$ and $G$ be a graph of order $n,$ with no $K_{2,t}$ minor. If $n>400t^{6}$, then the spectral radius $muleft( Gright) $ satisfies [ muleft( Gright) leqfrac{t-1}{2}+sqrt{n+frac{t^{2}-2t-3}{4}}, ] with equality if and only if $nequiv1$ $(ope
Let $G$ be a simple graph with vertex set $V(G) = {v_1 ,v_2 ,cdots ,v_n}$. The Harary matrix $RD(G)$ of $G$, which is initially called the reciprocal distance matrix, is an $n times n$ matrix whose $(i,j)$-entry is equal to $frac{1}{d_{ij}}$ if $i ot
This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More th