On some variations of extremal graph problems
Let \(\mathcal P\) be a hereditary graph property and let \(M(n,{\mathcal P})=\{G\in{\mathcal P}\bigm| | V_G| =n\), and \(G+e\not\in{\mathcal P}\) for any \(e\not\in E_G\}\). Denote by \(\text{ex} (n,{\mathcal P})\) and \(\text{sat} (n,{\mathcal P})\) the maximum and minimum values of \(| E_G| \) over \(G\in M(n,{\mathcal P})\). It is known that the behavior of \(\text{ex} (n,{\mathcal P})\) is monotone while \(\text{sat} (n,{\mathcal P})\) is not in general. Furthermore, if \(\mathcal L\) is the set of all hereditary properties, then \(({\mathcal L},\subseteq)\) is a distributive lattice. The authors provide several criteria of monotonicity of \(\text{sat} (n,{\mathcal P})\) in this lattice. By using the properties of \({\mathcal L}\), they prove some upper bounds for this number in the interval \(({\mathcal O}_k,{\mathcal I}_k)\) of \({\mathcal L}\). Here \({\mathcal O}_k\) is the class of graphs whose components have at most \(k+1\) vertices and \({\mathcal I}_k\) are ones which do not contain \(K_{k+2}\). Concerning the exact values of the numbers in question it is shown that under some weak assumption on the connectivity one has \(\text{sat} (n,{\mathcal P})= n-1\) for \({\mathcal D}_1\subseteq {\mathcal P}\subseteq {\mathcal I}_1\), where \({\mathcal D}_1\) is the class of \(1\)-degenerate graphs. For two further lattice intervals the exact values of \(\text{ex} (n,{\mathcal P})\) are presented.
- Some extremal problems of graphs with local constraints
- Weak saturation numbers of complete bipartite graphs in the clique
- The constructions and the judgement algorithms about G-extremal graphs and G-near-extremal graphs
- Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille
- scientific article; zbMATH DE number 3910425 (Why is no real title available?)
- Some extremal problems for hereditary properties of graphs
- scientific article; zbMATH DE number 1156579 (Why is no real title available?)
- A note on extremal results on directed acyclic graphs
- scientific article; zbMATH DE number 3298603 (Why is no real title available?)
- Weakly saturated hypergraphs and a conjecture of Tuza
- Size of weakly saturated graphs
This page was built for publication: On some variations of extremal graph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4209933)
