Linked graphs with restricted lengths (Q933678)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linked graphs with restricted lengths |
scientific article |
Statements
Linked graphs with restricted lengths (English)
0 references
24 July 2008
0 references
Given positive integers \(m_1, m_2, \dots, m_k\), a graph \(G\) is modulo \((m_1, m_2, \ldots, m_k)\)-linked if given any set of \(2k\) vertices \(x_1, x_2, \dots, x_k, y_1, y_2, \ldots, y_k\) of \(G\) there are \(k\) vertex disjoint paths \(P_i(x_i, y_i)\) from \(x_i\) to \(y_i\) for \(1 \leq i \leq k\), such that for any \(k\)-tuple of positive integers \((d_1, d_2, \dots, d_k)\) the length of \(P_i\) is congruent to \(d_i\) modulo \(m_i\). The authors show that if \((m_1, m_2, \dots, m_k)\) is a \(k\)-tuple of \(odd\) positive integers and \(G\) is a \((14(m_1 + m_2 + \cdots + m_k) - 4k + 36)\)-connected graph, then \(G\) is modulo \((m_1, m_2, \ldots, m_k)\)-linked. This improves the results of \textit{C. Thomassen} in [J. Graph Theory 7, 261--271 (1983; Zbl 0515.05052)].
0 references
connectivity
0 references
linkage
0 references
bipartite index
0 references
sumset
0 references
0 references