Name
Abstract | ||
|---|---|---|
Let G be a nontrivial connected graph with an edge-coloring c: E(G) -> {1, 2, ... , q}, q is an element of N, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S subset of V(G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V(G) is called the k-rainbow index of G, denoted by rx(k)(G). In this paper, we first determine the graphs of size m whose 3-rainbow index equals m, m - 1, m - 2 or 2. We also obtain the exact values of rx(3)(G) when G is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for rx(3)(G) when G is 2-connected and 2-edge connected. Graphs G for which rx(3)(G) attains this upper bound are determined. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.7151/dmgt.1780 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
rainbow tree,S-tree,k-rainbow index | Graph,Discrete mathematics,Combinatorics,Multipartite,Vertex (geometry),Upper and lower bounds,Bipartite graph,Connectivity,Rainbow,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 1 | 1234-3099 |
Citations | PageRank | References |
5 | 0.78 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lily Chen | 1 | 49 | 6.36 |
| Xueliang Li | 2 | 737 | 103.78 |
| Kang Yang | 3 | 78 | 19.31 |
| Yan Zhao | 4 | 9 | 2.63 |