Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn potentially $K_{r+1}-U$-graphical Sequences
368
0
0.0
(
0
)
Ask ChatGPT about the research
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)
rate research
Read More
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
