On the existence of \((k,l)\)-critical graphs (Q1377731): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q589833 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Stelian Mihalas / rank | |||
Normal rank |
Revision as of 18:04, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the existence of \((k,l)\)-critical graphs |
scientific article |
Statements
On the existence of \((k,l)\)-critical graphs (English)
0 references
8 July 1998
0 references
Let \(G=(V,E)\) be a graph with connectivity \(\kappa (G)=k\). A set \(X \subseteq V\) with \(|V-X |\geq k+1\) is called a fragment if the number of neighbors of \(X\) in \(V\setminus X\) is \(k\). Let \(W\subseteq V\) be such that \(W\cap X\neq \varnothing\) for each fragment \(X\) of \(G\). Then \(G\) is defined to be locally \((k,l)\)-critical if \(\kappa(G-W')= k-|W'|\) holds for every \(W'\subseteq W\) with \(|W'|<l\). The paper gives a short proof of a recent theorem of Su, stating that every non-complete \(W\)-locally \((k,l)\)-critical graph has \((2l+2)\) distinct ends and \(|W|\geq 2l+2\). This result implies a conjecture of Slater: there exist no \((k,l)\)-critical graphs with \(2l>k\), except \(K_{k+1}\).
0 references
critical graph
0 references
connectivity
0 references
fragment
0 references