Graph saturation in multipartite graphs

DOI10.4310/JOC.2016.V7.N1.A1MaRDI QIDQ5963384zbMATH OpenOpenAlexFDO

Authors Michael Ferrara, Michael Jacobson, Florian Pfender, Paul S. Wenger

Publication date 19 February 2016

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

saturation numbersaturated graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: Let $G$ be a fixed graph and let $mathcalF$ be a family of graphs. A subgraph $J$ of $G$ is $mathcalF$-saturated if no member of $mathcalF$ is a subgraph of $J$, but for any edge $e$ in $E(G)-E(J)$, some element of $mathcalF$ is a subgraph of $J+e$. We let $extex(mathcalF,G)$ and $extsat(mathcalF,G)$ denote the maximum and minimum size of an $mathcalF$-saturated subgraph of $G$, respectively. If no element of $mathcalF$ is a subgraph of $G$, then $extsat(mathcalF,G)=extex(mathcalF,G)=|E(G)|$. In this paper, for $kge3$ and $nge100$ we determine $extsat(K_3,K_k^n)$, where $K_k^n$ is the complete balanced $k$-partite graph with partite sets of size $n$. We also give several families of constructions of $K_t$-saturated subgraphs of $K_k^n$ for $tge4$. Our results and constructions provide an informative contrast to recent results on the edge-density version of $extex(K_t,K_k^n)$ from [A. Bondy, J. Shen, S. Thomass'e, and C. Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121--131] and [F. Pfender, Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), no. 4, 483--495].

Recommendations

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

Cited in

(17)

• Rainbow Saturation for Complete Graphs
• Saturated boundary \(k\)-alliances in graphs
• A note on minimum \(K_{2,3}\)-saturated graphs
• Saturation in Fuzzy Graphs
• Linearity of saturation for Berge hypergraphs
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• Partite saturation problems
• Saturation numbers in tripartite graphs
• On \((\mathrm{K}_t-e)\)-saturated graphs
• Partite saturation of complete graphs
• Min-max and max-min graph saturation parameters
• The partite saturation number of spider
• Saturation in random graphs
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph
• Saturation in Kneser graphs
• scientific article; zbMATH DE number 3939391 (Why is no real title available?)
• The saturation function of complete partite graphs

This page was built for publication: Graph saturation in multipartite graphs

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