2021/07/28 by Meiqiao Zhang, Zhang, Meiqiao, Fengming Dong +1 · 1 citation
Mathematics · #05C05 #05C15 #05C55 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C55
paper · pdf · doi:10.48550/arxiv.2107.13196
20 pages, 2 figures
arxiv created 2021/07/28 · arxiv updated 2021/07/29
Let G be a complete multi-partite graph of order n. In this paper, we consider the anti-Ramsey number ar(G,Tq) with respect to G and the set Tq of trees with q edges, where 2≤ q≤ n-1. For the case q=n-1, the result has been obtained by Lu, Meier and Wang. We will extend it to q<n-1. We first show that ar(G,Tq)=ℓq(G)+1, where ℓq(G) is the maximum size of a disconnected spanning subgraph H of G with the property that any two components of H together have at most q vertices. Using this equality, we obtain the exact values of ar(G,Tq) for n-3≤ q≤ n-1. We also compute ar(G,Tq) by a simple algorithm when (4n-2)/5≤ q≤ n-1.