No Arabic abstract
Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). We use the symbol $Z_4$ to denote $K_4-P_2.$ A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $sigma(S)geq sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $sigma (K_{r+1}-U, n)$ for $ngeq 5r+18, r+1 geq k geq 7,$ $j geq 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3 bigcup P_3$ but not contains a cycle on 4 vertices and not contains $Z_4$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $(K_{3} bigcup P_{3})$ but not contains a cycle on 4 vertices and not contains $Z_4$. (for example, $C_3bigcup C_{i_1} bigcup C_{i_2} bigcup >... bigcup C_{i_p}$ $(i_j eq 4, j=2,3,..., p, i_1 geq 5)$, $C_3bigcup P_{i_1} bigcup P_{i_2} bigcup ... bigcup P_{i_p}$ $(i_1 geq 3)$, $C_3bigcup P_{i_1} bigcup C_{i_2} bigcup >... bigcup C_{i_p}$ $(i_j eq 4, j=2,3,..., p, i_1 geq 3)$, etc)
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-partite graph. Furedi gave a short proof that one can choose alpha=epsilon. We give a bound for the relationship of alpha and varepsilon which is asymptotically sharp as epsilon to 0.
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 minimum value of $rholeft( Gright) $ for $r=2$, and found an asymptotically tight bound on $rholeft( Gright) $ for $rgeq3.$ They also conjectured that [ rholeft( Gright) >rholeft( S_{n,r-1}right) , ] unless $G=S_{n,r-1}.$ In this note their conjecture is proved.
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$.
Given graphs $G, H_1, H_2$, we write $G rightarrow ({H}_1, H_2)$ if every ${$red, blue$}$-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G rightarrow ({H}_1, H_2)$, but $G+erightarrow ({H}_1, H_2)$ for every edge $e$ in $overline{G}$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(K_t, K_{1,k})$-co-critical graphs on $n$ vertices. We prove that for all $tge3$ and $kge 3$, there exists a constant $ell(t, k)$ such that, for all $n ge (t-1)k+1$, if $G$ is a $(K_t, K_{1,k})$-co-critical graph on $n$ vertices, then $$ e(G)ge left(2t-4+frac{k-1}{2}right)n-ell(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{3, 4,5}$ and all $kge3$ and $nge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t, K_{1,k})$-co-critical graphs for $tge6$. We also obtain the sharp bound for the size of $(K_3, K_{1,3})$-co-critical graphs on $nge13$ vertices by showing that all such graphs have at least $3n-4$ edges.
One of the simplest ways to decide whether a given finite sequence of positive integers can arise as the degree sequence of a simple graph is the greedy algorithm of Havel and Hakimi. This note extends their approach to directed graphs. It also studies cases of some simple forbidden edge-sets. Finally, it proves a result which is useful to design an MCMC algorithm to find random realizations of prescribed directed degree sequences.