Abstract | ||
---|---|---|
A graph G is k-linked if G has at least 2k vertices, and for every sequence x"1,x"2,...,x"k,y"1,y"2,...,y"k of distinct vertices, G contains k vertex-disjoint paths P"1,P"2,...,P"k such that P"i joins x"i and y"i for i=1,2,...,k. Moreover, the above defined k-linked graph G is modulo(m"1,m"2,...,m"k)-linked if, in addition, for any k-tuple (d"1,d"2,...,d"k) of natural numbers, the paths P"1,P"2,...,P"k can be chosen such that P"i has length d"i modulo m"i for i=1,2,...,k. Thomassen showed that, for each k-tuple (m"1,m"2,...,m"k) of odd positive integers, there exists a natural number f(m"1,m"2,...,m"k) such that every f(m"1,m"2,...,m"k)-connected graph is modulo(m"1,m"2,...,m"k)-linked. For m"1=m"2=...=m"k=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo(2,2,...,2)-linked or there is X@?V(G) such that |X|==2. Our results generalize several known results on parity-linked graphs. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.jctb.2007.11.004 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
linked graph,distinct vertex,known result,bipartite index,restricted length,natural number g,linkage,connectivity,paths p,k-linked graph,parity-linked graph,connected graph,natural number,k vertex-disjoint paths p,graph g,sumset,upper bound,indexation | Integer,Discrete mathematics,Combinatorics,Natural number,Existential quantification,Vertex (geometry),Modulo,Bipartite graph,Sumset,Function composition,Mathematics | Journal |
Volume | Issue | ISSN |
98 | 4 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
G. Chen | 1 | 32 | 8.36 |
Yuan Chen | 2 | 0 | 0.34 |
Shuhong Gao | 3 | 469 | 47.50 |
Zhiquan Hu | 4 | 46 | 9.31 |