A Linear Time Algorithm for Cubic Subgraph of Halin Graphs

摘要

In this paper, we design a linear time algorithm to determine whether a Halin graph H has a cubic subgraph H*. If H has, then the algorithm finds a cubic subgraph H* in H; otherwise the algorithm answers "No".