On the existence of \((k,l)\)-critical graphs (Q1377731): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: On the optimal vertex-connectivity augmentation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eine Eigenschaft der Atome endlicher Graphen / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220626 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On k-critical, n-connected graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On locally \(k\)-critically \(n\)-connected graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fragments in <i>k</i>critical <i>n</i>‐connected graphs / rank | |||
Normal rank |
Revision as of 10:31, 28 May 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