zbMATH — the first resource for mathematics

Path extendability of \(s\)-vertex connected graphs. (English) Zbl 1240.05164
Summary: Let \(G\) be a simple graph. \(G\) is called \(s\)-vertex connected if every induced subgraph with \(s\) vertices is connected but there exists an induced subgraph with \(s-1\) vertices that is not connected, where \(s\geq 3\). A path \(P\) is extendable if there exists another path \(P'\) such that \(V (P')\supset V (P)\) and \(|V (P')|=|V (P)|+1\). A graph \(G\) is said to be fully path extendable if its diameter is at most two and every path \(P\) with \(|V (P)|<|V (G)|\) is extendable. In this paper, we prove that an \(s\)-vertex connected graph whose order is not less than \(2s-1\) is fully path extendable.
05C38 Paths and cycles
05C40 Connectivity