Linear forest

In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,: 200  or a disjoint union of nontrivial paths.: 246  Equivalently, it is an acyclic and claw-free graph.: 130, 131  An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.: 310 : 107  An undirected graph has Colin de Verdière graph invariant at most 1 if and only if it is a (node-)disjoint union of paths, i.e. it is linear.: 13, 19–21 : 29, 35, 67 (3, 6, 29)  Any linear forest is a subgraph of the path graph with the same number of vertices.: 55 

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.