Rainbow trees in graphs and generalized connectivity
Rainbow trees in graphs and generalized connectivity
复制标题
DOI：
10.1002/net.20339
复制
发表时间：
2010-07
期刊：
影响因子：
2.1
通讯作者：
G. Chartrand;Futaba Fujie-Okamoto;Ping Zhang
中科院分区：
文献类型：
--
作者：
G. Chartrand;Futaba Fujie-Okamoto;Ping Zhang
一棵边着色树T是一棵彩虹树，如果T的任何两条边都不被赋予相同的颜色。设G是一个n阶非平凡连通图，k是一个2 ≤ k ≤ n的整数. G的一个k-彩虹染色是G的一个边染色，它具有这样的性质：对于G的每个k个顶点的集合S，在G中存在一个彩虹树T，使得S ≠ V（T）。G的k-彩虹染色所需的最少颜色数是G的k-彩虹指数。对于任意两个整数k和n ≥ 3，其中3 ≤ k ≤ n，确定n阶单圈图的k-彩虹指数。对于n阶连通图G中的顶点集S，称G中的树的集合{T1，T2，.，T <$}是内部不交的连通S，如果这些树是成对边不交的，并且V（Ti）<$V（Tj）= S，对于每个不同整数对i，j，1 ≤ i，j ≤ n。对于整数k，其中2 ≤ k ≤ n，G的k-连通度κk（G）是最大正整数k，使得对于G的k个顶点的集合S，G至少包含3棵内部不交树连接S。证明了对于任意整数对k，n，其中2 ≤ k ≤ n，有κk（Kn）=n− k/2 <$。对于n阶非平凡连通图G，对于2 ≤ k ≤ n且1 ≤ k ≤ κk（G）的整数k和k，G的（k，k）-彩虹指数rxk，k（G）是G的边染色所需的最小颜色数，使得对于G的k个顶点的集合S，G至少包含3棵内部不相交的彩虹树连接S。当n ≤ 6时，对于所有可能的值k和k，确定数rxk，k（Kn）。还证明了对n ∈ {1，2}，rx 3，n（Kn）= 3，对所有n ≥ 6.© 2009威利期刊公司.网络，2010年
An edge‐colored tree T is a rainbow tree if no two edges of T are assigned the same color. Let G be a nontrivial connected graph of order n and let k be an integer with 2 ≤ k ≤ n. A k‐rainbow coloring of G is an edge coloring of G having the property that for every set S of k vertices of G, there exists a rainbow tree T in G such that S ⊆ V(T). The minimum number of colors needed in a k‐rainbow coloring of G is the k‐rainbow index of G. For every two integers k and n ≥ 3 with 3 ≤ k ≤ n, the k‐rainbow index of a unicyclic graph of order n is determined. For a set S of vertices in a connected graph G of order n, a collection {T1,T2,…,Tℓ} of trees in G is said to be internally disjoint connecting S if these trees are pairwise edge‐disjoint and V(Ti) ∩ V(Tj) = S for every pair i,j of distinct integers with 1 ≤ i,j ≤ ℓ. For an integer k with 2 ≤ k ≤ n, the k‐connectivity κk(G) of G is the greatest positive integer ℓ for which G contains at least ℓ internally disjoint trees connecting S for every set S of k vertices of G. It is shown that κk(Kn)=n−⌈k/2⌉ for every pair k,n of integers with 2 ≤ k ≤ n. For a nontrivial connected graph G of order n and for integers k and ℓ with 2 ≤ k ≤ n and 1 ≤ ℓ ≤ κk(G), the (k,ℓ)‐rainbow index rxk,ℓ(G) of G is the minimum number of colors needed in an edge coloring of G such that G contains at least ℓ internally disjoint rainbow trees connecting S for every set S of k vertices of G. The numbers rxk,ℓ(Kn) are determined for all possible values k and ℓ when n ≤ 6. It is also shown that for ℓ ϵ {1, 2}, rx3,ℓ(Kn) = 3 for all n ≥ 6. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010