Linked graphs with restricted lengths
type: Item
instance of: scholarly article
title: Linked graphs with restricted lengths
zbMATH Open document ID: 1149.05024
author: Guantao Chen
author: Yuan Chen
author: Shuhong Gao
author: Zhiquan Hu
published in: Journal of Combinatorial Theory. Series B
publication date: 2008-07-24T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5303725
zbMATH Keywords: connectivity
zbMATH Keywords: linkage
zbMATH Keywords: bipartite index
zbMATH Keywords: sumset
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: j.jctb.2007.11.004
OpenAlex ID: W2035541146
cites work: Ordered and linked chordal graphs
cites work: Cycles Modulo k
cites work: Cycles and semi-topological configurations
cites work: Highly linked graphs
cites work: Q4376500
cites work: Q5315023
cites work: Q4121920
cites work: On the addition of residue classes mod p
cites work: Distribution of cycle lengths in graphs
cites work: On the odd-minor variant of Hadwiger's conjecture
cites work: Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
cites work: K-linked graphs with girth condition
cites work: On Sufficient Degree Conditions for a Graph to be $k$-linked
cites work: Highly parity linked graphs
cites work: On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
cites work: Topological subgraphs in graphs of large girth
cites work: Q4895030
cites work: An addition theorem for the elementary abelian group
cites work: An improved linear edge bound for graph linkages
cites work: Graph decomposition with applications to subdivisions and path systems modulo k
cites work: The Erdős-Pósa property for odd cycles in graphs of large connectivity
cites work: On arithmetic progressions of cycle lengths in graphs
DOI: 10.1016/J.JCTB.2007.11.004
description: scientific article; zbMATH DE number 5303725