Sharp 3-Path Isolation Bound for Subcubic Graphs
The 3-path isolation number of a graph is the fewest vertices whose closed neighbourhood meets every path on three vertices, leaving no two edges adjacent. This result determines the sharp bound for subcubic graphs (maximum degree three): every connected subcubic graph with no induced 6-cycle needs at most n/4 such vertices, with exactly twelve small exceptional graphs. The learner sees how forbidding induced 6-cycles improves the general 2n/7 bound and how extremal families certify sharpness.
2501.00419
For a connected graph G, the 3-path isolation number iota(G,P3) is the size of the smallest vertex set D whose closed neighbourhood meets every 3-vertex path, equivalently so that deleting the closed…