Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees in All Graphs

Abstract: An edge-colored graph

G

is called extit{rainbow} if every edge of

G

receives a different color. Given any host graph

G

, the extit{anti-Ramsey} number of

t

edge-disjoint rainbow spanning trees in

G

, denoted by

r (G, t)

, is defined as the maximum number of colors in an edge-coloring of

G

containing no

t

edge-disjoint rainbow spanning trees. For any vertex partition

P

, let

E (P, G)

be the set of non-crossing edges in

G

with respect to

P

. In this paper, we determine

r (G, t)

for all host graphs

G

:

r (G, t) = | E (G) |

if there exists a partition

P_{0}

with

| E (G) | - | E (P_{0}, G) | < t (| P_{0} | - 1)

; and

r (G, t) = m a x_{P c o l o n | P | g e q 3} | E (P, G) | + t (| P | - 2)

otherwise. As a corollary, we determine

r (K_{p, q}, t)

for all values of

p, q, t

, improving a result of Jia, Lu and Zhang.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees in All Graphs