Links in edge-colored graphs

被引：5
作者：
Becu, J. M. [2 ]
Dah, M. [2 ]
Manoussakis, Y. [2 ]
Mendy, G. [1 ,2 ]
机构：
[1] Ecole Super Polytech Dakar, Dept Genie Informat, LIRT, Dakar, Senegal
[2] Univ Paris 11, LRI, F-91405 Orsay, France
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2010年 / 31卷 / 02期
关键词：
EULERIAN CYCLES; PATHS;
D O I：
10.1016/j.ejc.2009.03.021
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph is k-linked (k-edge-linked), k >= 1, if for each k pairs of vertices x(1), y(1), ..., x(k), y(k), there exist k pairwise vertex-disjoint (respectively edge-disjoint) paths, one per pair x(i) and y(i), i = 1, 2, ..., k. Here we deal with the properly edge-colored version of the k-linked (k-edge-linked) problem in edge-colored graphs. In particular, we give conditions on colored degrees and/or number of edges, sufficient for an edge-colored multigraph to be k-linked (k-edge-linked). Some of the results obtained are the best possible. Related conjectures are proposed. (C) 2009 Published by Elsevier Ltd
引用
收藏
页码：442 / 460
页数：19
相关论文
共 17 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]  
Bang-Jensen J., 2002, DIGRAPHS THEORY ALGO, P5
[3]  
Bankfalvi, 1968, THEORY GRAPHS, P11
[4]  
Benkouar A, 1996, RAIRO-RECH OPER, V30, P417
[5]  
BOLLOBAS B, 1976, ISRAEL J MATH, V23, P126, DOI 10.1007/BF02756791
[6]   THE DIRECTED SUBGRAPH HOMEOMORPHISM PROBLEM [J].
FORTUNE, S ;
HOPCROFT, J ;
WYLLIE, J .
THEORETICAL COMPUTER SCIENCE, 1980, 10 (02) :111-121
[7]   GRAPH FOLDING AND PROGRAMMABLE LOGIC ARRAY [J].
HU, TC ;
KUO, YS .
NETWORKS, 1987, 17 (01) :19-37
[8]   On sufficient degree conditions for a graph to be k-linked [J].
Kawarabayashi, Ken-Ichi ;
Kostochka, Alexandr ;
Yu, Gexin .
COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (05) :685-694
[9]   Linkedness and ordered cycles in digraphs [J].
Kuehn, Daniela ;
Osthus, Deryk .
COMBINATORICS PROBABILITY & COMPUTING, 2008, 17 (03) :411-422
[10]   ALTERNATING PATHS IN EDGE-COLORED COMPLETE GRAPHS [J].
MANOUSSAKIS, Y .
DISCRETE APPLIED MATHEMATICS, 1995, 56 (2-3) :297-309
12