Path extendable graphs (Q805629): Difference between revisions

A path P in graph G is extendable if there exists a path \(P'\) in G with the same endvertices as P and the vertex set of \(P'\) consists of V(P) together with one additional vertex. A graph is path extendable if every non-Hamiltonian path in G is extendable. Graph G is fully path extendable if it is extendable and has diameter at most two. A graph is panconnected if for each pair of vertices u, v, there exists a u-v path of length 1 for each integer 1, d(u,v)\(\leq 1\leq p-1\). A graph G is PLD-maximal if for each 1, \(2\leq 1\leq p-1\) there exists a path of length 1 connecting each pair of distance vertices of G. It follows immediately that every path extendable graph is panconnected and every fully path extendable graph is PLD-maximal. In this paper sufficient conditions for a graph to be path extendable or fully path extendable are investigated.