Graphs G Where G-N[v] is a Tree for Each Vertex v.

A given graph H is called realizable by a graph G if G [ N (v) ] ≅ H for every vertex v of G. The Trahtenbrot-Zykov problem says that which graphs are realizable? We consider a problem somewhat opposite in a more general setting. Let F be a family of graphs: to characterize all graphs G such that G - N [ v ] ∈ F for every vertex v of G. Let T m be the set of all trees of size m ≥ 0 for a fixed nonnegative integer m, P = { P t : t > 0 } and S = { K 1 , t : t ≥ 0 } . We show that for a connected graph G with its complement G ¯ being connected, G - N [ v ] ∈ T m for each v ∈ V (G) if and only if one of the following holds: G - N [ v ] ≅ K 1 , m for each v ∈ V (G) , or G - N [ v ] ≅ P m + 1 for each v ∈ V (G) . Indeed, the graphs with later two properties are characterized by the same authors very recently (Graphs G in which G - N [ v ] has a prescribed property for each vertex v, Discrete Appl. Math., In press.). In addition, we characterize all graphs G such that G - N [ v ] ∈ S for each v ∈ V (G) and all graphs G such that G - N [ v ] ∈ P for each v ∈ V (G) . This solves an open problem raised by Yu and Wu (Graphs in which G - N [ v ] is a cycle for each vertex v, Discrete Math. 344 (2021) 112519). Finally, a number of conjectures are proposed for the perspective of the problem. [ABSTRACT FROM AUTHOR]