On decycling and forest numbers of Cartesian products of trees

2025/01/12 by Ghalavand, Ali, Klavžar, Sandi, Yang, Ning
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2501.06902

Abstract

The decycling number ∇(G) of a graph G is the minimum number of vertices that must be removed to eliminate all cycles in G. The forest number f(G) is the maximum number of vertices that induce a forest in G. So ∇(G) + f(G) = |V(G)|. For the Cartesian product T \square T' of trees T and T' it is proved that ∇(S_n \square S_n') ≤ ∇(T \square T'), thus resolving the conjecture of Wang and Wu asserting that f(T \square T') ≤ f(S_n \square S_n'). It is shown that ∇(T \square T') ≥ |V(T)| - 1 and the equality cases characterized. For prisms over trees, it is proved that ∇(T \square K₂) = α'(T), and for arbitrary graphs G₁ and G₂, it is proved that ∇(G₁ \square G₂) ≥ α'(G₁) α'(G₂), where α' is the matching number.

Related

• On Maximum Induced Forests of the Balanced Bipartite Graphs
• Decycling Number of Linear Graphs of Trees
• Cartesian Product and Acyclic Edge Colouring
• Decycling cubic graphs
• Line k-Arboricity in Product Networks