k-szorosan összefüggő gráf
olyan gráf, melyben található út bármely két csúcs között még tetszőleges k‒1 csúcs elhagyása után is / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén G összefüggő gráfot akkor nevezünk k-szorosan összefüggő, k-összefüggő (vagy k-szorosan csúcsösszefüggő) gráfnak, ha több mint k csúcsa van, és kevesebb mint k csúcs eltávolítása után minden esetben összefüggő marad (minimális elvágó csúcshalmazának mérete k).
Egy gráf összefüggősége vagy csúcsösszefüggősége (jelölése: κ(G)) az a legnagyobb k szám, amire igaz, hogy a gráf k-szorosan csúcsösszefüggő. Konvenció szerint a Kn teljes gráf összefüggősége n − 1, az üres gráf összefüggősége pedig 0. Adott gráfban a csúcsösszefüggőség, az élösszefüggőség és a minimális fokszám között fennáll, hogy κ(G) ≤ κ’(G) ≤ δ(G).