Partite saturation of complete graphs

DOI10.1137/18M1166559MaRDI QIDQ5204066zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

saturationcomplete graphspartite saturation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

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.

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

Cites work

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

Cited in

(8)

• Rainbow Saturation for Complete Graphs
• Exact bounds for some hypergraph saturation problems
• Graph saturation in multipartite graphs
• scientific article; zbMATH DE number 844141 (Why is no real title available?)
• Partite saturation problems
• Saturation numbers in tripartite graphs
• Complete subgraphs in a multipartite graph
• The saturation function of complete partite 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)