Linked graphs with restricted lengths

DOI10.1016/J.JCTB.2007.11.004MaRDI QIDQ933678zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Yuan Chen, Shuhong Gao, Zhiquan Hu

Publication date 24 July 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.11.004

zbMATH Keywords

bipartite indexconnectivitylinkagesumset

Mathematics Subject Classification ID

Paths and cycles (05C38)

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)].

Recommendations

• On Modulo Linked Graphs
• Highly linked graphs
• scientific article; zbMATH DE number 1439448
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• Highly parity linked graphs

Cites work

• An addition theorem for the elementary abelian group
• An improved linear edge bound for graph linkages
• Cycles and semi-topological configurations
• Cycles Modulo k
• Distribution of cycle lengths in graphs
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Graph decomposition with applications to subdivisions and path systems modulo k
• Highly linked graphs
• Highly parity linked graphs
• scientific article; zbMATH DE number 3547317 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 933467 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• K-linked graphs with girth condition
• On arithmetic progressions of cycle lengths in graphs
• On Sufficient Degree Conditions for a Graph to be k-linked
• On the addition of residue classes mod p
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• On the odd-minor variant of Hadwiger's conjecture
• Ordered and linked chordal graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• Topological subgraphs in graphs of large girth

Cited in

(2)

• On Modulo Linked Graphs
• Coloring hypergraphs with excluded minors

This page was built for publication: Linked graphs with restricted lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q933678)