Document Type
Lecture
Publication Date
4-13-2011
Abstract
A graph G is k-linked if G has at least 2k vertices, and for every sequence x1 x2 yk of distinct vertices, G contains k vertex-disjoint paths P1P2 Pk such that Pi joins xi and yi for i = 12 k. Moreover, the above de ned k-linked graph G is k-linked modulo (m1m2 in addition, for any k-tuple (d1 d2 mk) if, dk) of natural numbers, the paths P1P2 12 Pk can be chosen such that Pi has length di modulo mi for i = k. Thomassen showed that there exists a function f(m1m2 such that every f(m1m2 (m1m2 mk)-connected graph is k-linked modulo mk) mk) provided all mi are odd. For even moduli, he showed in another article that there exists a natural number g(22 2) such that every g(22 2)-connected graph is k-linked modulo (22 any 4k 3 vertices leaves a non-bipartite graph. In this talk, we show linear upper bounds for f(m1m2 g(m1m2 mk) in terms of m1m2 2) if deleting mk) and mk, respectively. Our results generalize several known results on k-parity-linked graphs. This is a joint work with Guantao Chen, Yuan Chen and Shuhong Gao.
Relational Format
presentation
Recommended Citation
Hu, Zhiquan, "Linked Graph with Modular Constraints" (2011). Combinatorics Seminar. 71.
https://egrove.olemiss.edu/math_combinatorics/71
