Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe exact minimum number of triangles in graphs of given order and size
155
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turan, Rademacher solved the first non-trivial case of this problem in 1941. The problem was revived by ErdH{o}s in 1955; it is now known as the ErdH{o}s-Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from~$1$, which in this range confirms a conjecture of Lovasz and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.
rate research
Read More
Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smaller than n^r/(n^2-2m). The solution is based on a constraint minimization of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.
We study the maximum number $ex(n,e,H)$ of copies of a graph $H$ in graphs with given number of vertices and edges. We show that for any fixed graph $H$, $ex(n,e,H)$ is asymptotically realized by the quasi-clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.
An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. The $proper$ $connection$ $number$ of a connected graph $G$, denoted by $pc(G)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Susan A. van Aardt et al. gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note, %optimizes the boundary of the number of edges %we study the $proper$ $connection$ $number$ is under the conditions of adding the minimum degree and optimizing the number of edges. our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $kgeq3$. If $|E(G)|geq binom{n-m-(k+1-m)(delta+1)}{2} +(k+1-m)binom{delta+1}{2}+k+2$, then $pc(G)leq k$, where $m$ takes the value $t$ if $delta=1$ and $lfloor frac{k}{delta-1} rfloor$ if $deltageq2$. Furthermore, if $k=2$ and $delta=2$, %(i.e., $|E(G)|geq binom{n-5}{2} +7$) $pc(G)leq 2$, except $Gin {G_{1}, G_{n}}$ ($ngeq8$), where $G_{1}=K_{1}vee 3K_{2}$ and $G_{n}$ is obtained by taking a complete graph $K_{n-5}$ and $K_{1}vee (2K_{2}$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}vee (2K_{2}$) being joined. If $k=2$, $delta geq 3$, we conjecture $pc(G)leq 2$, where $m$ takes the value $1$ if $delta=3$ and $0$ if $deltageq4$ in the assumption.
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
Given a digraph $D$ with $m$ arcs and a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$, we say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and no two vertices in $D$ have the same vertex-sum under $tau$, where the vertex-sum of a vertex $u$ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs, biregular bipartite graphs, and graphs with large maximum degree. In this paper, we establish more evidence for the aforementioned conjecture by studying antimagic orientations of graphs $G$ with independence number at least $|V(G)|/2$ or at most four. We obtain several results. The method we develop in this paper may shed some light on attacking the aforementioned conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
