Open Access. Powered by Scholars. Published by Universities.®
![Digital Commons Network](http://assets.bepress.com/20200205/img/dcn/DCsunburst.png)
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
On The P-Connectedness Of Graphs – A Survey, Luitpold Babel, Stephan Olariu
On The P-Connectedness Of Graphs – A Survey, Luitpold Babel, Stephan Olariu
Computer Science Faculty Publications
A graph is said to be p-connected if for every partition of its vertices into two non-empty, disjoint, sets some chordless path with three edges contains vertices from both sets in the partition. As it turns out, p-connectedness generalizes the usual connectedness of graphs and leads, in a natural way, to a unique tree representation for arbitrary graphs.
This paper reviews old and new results, both structural and algorithmic, about p-connectedness along with applications to various graph decompositions.