On (K_q,k) stable graphs with small k

MaRDI QIDQ456306zbMATH OpenFDO

Authors Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Adam Paweł Wojda

Publication date 24 October 2012

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

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p50

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

stable graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

Summary: A graph \(G\) is \((K_{q},k)\) stable if it contains a copy of \(K_{q}\) after deleting any subset of \(k\) vertices. In a previous paper we have characterized the \((K_q,k)\) stable graphs with minimum size for \(3 \leq q \leq 5\) and we have proved that the only \((K_q,k)\) stable graph with minimum size is \(K_{q+k}\) for \(q \geq 5\) and \(k \leq 3\). We show that for \(q \geq 6\) and \(k \leq \frac{q}{2}+1\) the only \((K_q,k)\) stable graph with minimum size is isomorphic to \(K_{q+k}\).

Recommendations

• On minimum (K_q, k) stable graphs
• On \((K_q,k)\) vertex stable graphs with minimum size
• On (K_q;k)-stable graphs
• (H,k) stable graphs with minimum size
• On \((C_n;k)\) stable graphs

Cited in

(7)

• On (K_q;k)-stable graphs
• On minimum (K_q, k) stable graphs
• (H,k) stable graphs with minimum size
• scientific article; zbMATH DE number 22658 (Why is no real title available?)
• On \((K_q,k)\) vertex stable graphs with minimum size
• A lower bound on the size of (H;1)-vertex stable graphs
• A generalization of an independent set with application to (K_q; k)-stable graphs

This page was built for publication: On \((K_{q},k)\) stable graphs with small \(k\)

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