דקל צור

A graph G is a 3-leaf power if there is a tree T and a bijective mapping f from V(G) to the set of leaves of T such that (u,v)∈E(G) if and only if the distance in T between f(u) and f(v) is at most 3 for every distinct u,v∈V(G). In the 3-LEAF POWER VERTEX DELETION (resp., 3-LEAF POWER COMPLETION) problem the input is a graph G and an integer k, and the goal is to decide whether G can be transformed into a 3-leaf power graph by deleting at most k vertices (resp., adding at most k edges). In this paper we give a kernel for 3-LEAF POWER VERTEX DELETION with O(k⁶) vertices and a kernel for 3-LEAF POWER COMPLETION with O(k²) vertices. Our results improve the previous O(k¹⁴)-vertices kernel for 3-LEAF POWER VERTEX DELETION [Ahn et al., 2023 [3]] and the O(k³)-vertices kernel for 3-LEAF POWER COMPLETION [Bessy et al., 2010 [5]].