Path extendability of \(s\)-vertex connected graphs. (English) Zbl 1240.05164

Bo, Xiangzhi; Meng, Jixiang

J. Xinjiang Univ., Nat. Sci. 27, No. 4, 405-407 (2010).

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.

MSC:

05C38	Paths and cycles
05C40	Connectivity

Keywords:

connectivity; \(s\)-vertex connected graphs; fully path extendable