Partite saturation of complete graphs

DOI10.1137/18M1166559zbMATH Open1428.05150arXiv1708.01607OpenAlexW2992720965WikidataQ126620472 ScholiaQ126620472MaRDI QIDQ5204066FDOQ5204066

Authors: António Girão, Teeradej Kittipassorn, Kamil Popielarz 

Publication date: 9 December 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study the problem of determining $sat(n,k,r)$, the minimum number of edges in a $k$-partite graph $G$ with $n$ vertices in each part such that $G$ is $K_r$-free but the addition of an edge joining any two non-adjacent vertices from different parts creates a $K_r$. Improving recent results of Ferrara, Jacobson, Pfender and Wenger, and generalizing a recent result of Roberts, we define a function $alpha(k,r)$ such that $sat(n,k,r)=alpha(k,r)n+o(n)$ as $nightarrowinfty$. Moreover, we prove that [ k(2r-4) le alpha(k,r) le �egin{cases} (k-1)(4r-k-6) & ext{ for }r le k le 2r-3, \(k-1)(2r-3) & ext{ for }k ge 2r-3, end{cases} ] and show that the lower bound is tight for infinitely many values of $r$ and every $kgeq2r-1$. This allows us to prove that, for these values, $sat(n,k,r)=k(2r-4)n+O(1)$ as $nightarrowinfty$. Along the way, we disprove a conjecture and answer a question of the first set of authors mentioned above.

Full work available at URL: https://arxiv.org/abs/1708.01607

Recommendations

• Graph saturation in multipartite graphs
• Partite saturation problems
• The saturation function of complete partite graphs
• Saturation numbers in tripartite graphs
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph

zbMATH Keywords

saturationcomplete graphspartite saturation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Saturated graphs with minimal number of edges
• A survey of minimum saturated graphs
• A Problem in Graph Theory
• On generalized graphs
• Title not available (Why is that?)
• On a Conjecture of Erdos, Hajnal and Moon
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Theorem on k-Saturated Graphs
• Saturated subgraphs of the hypercube
• Exact bounds for some hypergraph saturation problems
• \(K_{s,t}\)-saturated bipartite graphs
• Saturation numbers in tripartite graphs
• Graph saturation in multipartite graphs
• Saturation in the hypercube and bootstrap percolation
• Saturation in random graphs
• Minimum critical squarefree subgraph of a hypercube
• Partite saturation problems

Cited In (8)

• Exact bounds for some hypergraph saturation problems
• Graph saturation in multipartite graphs
• Title not available (Why is that?)
• Partite saturation problems
• Saturation numbers in tripartite graphs
• Complete subgraphs in a multipartite graph
• The saturation function of complete partite graphs
• Rainbow Saturation for Complete Graphs

This page was built for publication: Partite saturation of complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204066)