Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe saturation number of $C_6$
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is called $C_k$-saturated if $G$ is $C_k$-free but $G+e$ not for any $ein E(overline{G})$. The saturation number of $C_k$, denoted $sat(n,C_k)$, is the minimum number of edges in a $C_k$-saturated graph on $n$ vertices. Finding the exact values of $sat(n,C_k)$ has been one of the most intriguing open problems in extremal graph theory. In this paper, we study the saturation number of $C_6$. We prove that ${4n}/{3}-2 le sat(n,C_6) le {(4n+1)}/{3}$ for $nge9$, which significantly improves the existing lower and upper bounds for $sat(n,C_6)$.
rate research
Read More
A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the saturation number of complete partite graphs is one of the most important problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was shown to be $lfloorfrac{3n-5}{2}rfloor$ by Ollmann, and a shorter proof was later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that $sat(n, K_{2,3})= 2n-3$ for all $ngeq 5$. In this paper, we prove a conjecture of Pikhurko and Schmitt that $sat(n, K_{3,3})=3n-9$ when $n geq 9$.
For a fixed graph $F$ and an integer $t$, the dfn{rainbow saturation number} of $F$, denoted by $sat_t(n,mathfrak{R}(F))$, is defined as the minimum number of edges in a $t$-edge-colored graph on $n$ vertices which does not contain a dfn{rainbow copy} of $F$, i.e., a copy of $F$ all of whose edges receive a different color, but the addition of any missing edge in any color from $[t]$ creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that $sat_t(n,mathfrak{R}(P_ell))ge n-1$ for $ellge 4$ and $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell-1} rceil cdot binom{ell-1}{2}$ for $tge binom{ell-1}{2}$, where $P_ell$ is a path with $ell$ edges. In this short note, we improve the upper bounds and show that $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell} rceil cdot left({{ell-2}choose {2}}+4right)$ for $ellge 5$ and $tge 2ell-5$.
We study F-saturation games, first introduced by Furedi, Reimer and Seress in 1991, and named as such by West. The main question is to determine the length of the game whilst avoiding various classes of graph, playing on a large complete graph. We show lower bounds on the length of path-avoiding games, and more precise results for short paths. We show sharp results for the tree avoiding game and the star avoiding game.
We look at several saturation problems in complete balanced blow-ups of graphs. We let $H[n]$ denote the blow-up of $H$ onto parts of size $n$ and refer to a copy of $H$ in $H[n]$ as partite if it has one vertex in each part of $H[n]$. We then ask how few edges a subgraph $G$ of $H[n]$ can have such that $G$ has no partite copy of $H$ but such that the addition of any new edge from $H[n]$ creates a partite $H$. When $H$ is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger. Our main result is to calculate this value for $H=K_4$ when $n$ is large. We also give exact results for paths and stars and show that for $2$-connected graphs the answer is linear in $n$ whilst for graphs which are not $2$-connected the answer is quadratic in $n$. We also investigate a similar problem where $G$ is permitted to contain partite copies of $H$ but we require that the addition of any new edge from $H[n]$ creates an extra partite copy of $H$. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.
We prove that if the spectral radius of a graph G of order n is larger than the spectral radius of the r-partite Turan graph of the same order, then G contains various supergraphs of the complete graph of order r+1. In particular G contains a complete r-partite graph of size log n with one edge added to the first part. These results complete a project of Erdos from 1963. We also give corresponding stability results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
