Graph saturation in multipartite graphs

DOI10.4310/JOC.2016.V7.N1.A1zbMATH Open1331.05112arXiv1408.3137OpenAlexW2962679102MaRDI QIDQ5963384FDOQ5963384

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

Publication date: 19 February 2016

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

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].

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)

Cited In (13)

• Partite Saturation Problems
• Partite Saturation of Complete Graphs
• Saturated boundary \(k\)-alliances in graphs
• Saturation in Fuzzy Graphs
• Linearity of saturation for Berge hypergraphs
• 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 Numbers in Tripartite Graphs
• Title not available (Why is that?)
• The saturation function of complete partite graphs
• Rainbow Saturation for Complete 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)