Path extendable graphs

DOI10.1007/BF02651089MaRDI QIDQ805629zbMATH OpenOpenAlexFDO

Authors George R. T. Hendry

Publication date 1990

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02651089

zbMATH Keywords

fully path extendablepanconnectedPLD-maximal

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

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.

Recommendations

• Path graphs
• Endpoint extendable paths in dense graphs
• Paths in graphs
• Path extendability of s-vertex connected graphs
• A sufficient condition for path extendable graphs
• scientific article; zbMATH DE number 1286752
• Extending paths and degree sums in graphs
• Spanning paths in graphs
• Path-connectivity in graphs
• Path saturated graphs

Cites work

• A note on locally connected and Hamiltonian-connected graphs
• Connected, locally 2-connected,K1,3-free graphs are panconnected
• Extending cycles in graphs
• Hamilton connected graphs
• scientific article; zbMATH DE number 3550742 (Why is no real title available?)
• scientific article; zbMATH DE number 3625415 (Why is no real title available?)
• scientific article; zbMATH DE number 3192675 (Why is no real title available?)
• On path connected graphs
• On the Cube of a Graph
• On the hamiltonian path graph of a graph
• Path connected graphs
• Theory of path length distributions. I

Cited in

(8)

• Minimum degree and pan-\(k\)-linked graphs
• Connectivity and extendability in digraphs
• Path extendability and degree sum in graphs.
• Note on odd path extendable graphs
• A sufficient condition for path extendable graphs
• Path extendability of s-vertex connected graphs
• Endpoint extendable paths in dense graphs
• Extremal and degree conditions for path extendability in digraphs

This page was built for publication: Path extendable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805629)