2025/01/09 by Ali Ghalavand, Xueliang Li, Ghalavand, Ali +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2501.05145
openalex publication_date 2025/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∇(Sn \square Sn') ≤ ∇(T \square T'), thus resolving the conjecture of Wang and Wu asserting that f(T \square T') ≤ f(Sn \square Sn'). It is shown that ∇(T \square T') ≥min\ |V(T)|,|V(T')|\ - 1 and the equality cases characterized. For prisms over trees, it is proved that ∇(T \square K2) = α'(T), and for arbitrary graphs G1 and G2, it is proved that ∇(G1 \square G2) ≥ α'(G1) α'(G2), where α' is the matching number.