On the number of alternating paths in bipartite complete graphs

DOI10.1007/S00373-017-1771-XMaRDI QIDQ2014212zbMATH OpenOpenAlexFDO

Authors Patrick Bennett, Andrzej Dudek, Elliot Laforge

Publication date 10 August 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.04923

zbMATH Keywords

alternating connectivityalternating pathsHamming distanceinteger programsrandom colorings

Mathematics Subject Classification ID

Connectivity (05C40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Integer programming (90C10)

Abstract: Let $Csubseteq[r{]}^m$ be a code such that any two words of $C$ have Hamming distance at least $t$. It is not difficult to see that determining a code $C$ with the maximum number of words is equivalent to finding the largest $n$ such that there is an $r$-edge-coloring of $K_{m,n}$ with the property that any pair of vertices in the class of size $n$ has at least $t$ alternating paths (with adjacent edges having different colors) of length $2$. In this paper we consider a more general problem from a slightly different direction. We are interested in finding maximum $t$ such that there is an $r$-edge-coloring of $K_{m,n}$ such that any pair of vertices in class of size $n$ is connected by $t$ internally disjoint and alternating paths of length $2k$. We also study a related problem in which we drop the assumption that paths are internally disjoint. Finally, we introduce a new concept, which we call alternating connectivity. Our proofs make use of random colorings combined with some integer programs.

Recommendations

• \(M\)-alternating paths in \(n\)-extendable bipartite graphs
• On the number of alternating paths in random graphs
• A note on internally disjoint alternating paths in bipartite graphs
• Alternating paths in edge-colored complete graphs
• scientific article; zbMATH DE number 1786512
• On the basis number of some complete bipartite graphs
• scientific article; zbMATH DE number 638682
• An extremal problem for paths in bipartite graphs
• The path partition problem and related problems in bipartite graphs
• scientific article; zbMATH DE number 426164

Cites work

• A property of the colored complete graph
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating Hamiltonian cycles
• Counting paths in digraphs
• Extensions of results on rainbow Hamilton cycles in uniform hypergraphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• scientific article; zbMATH DE number 1209696 (Why is no real title available?)
• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Multicoloured Hamilton cycles
• Rainbow Hamilton cycles in uniform hypergraphs

Cited in

(5)

• Alternating paths in edge-colored complete graphs
• On the number of alternating paths in random graphs
• scientific article; zbMATH DE number 1786512 (Why is no real title available?)
• M-alternating paths and the construction of defect \(n\)-extendable bipartite graphs with different connectivities
• Graphs with no M-alternating paths between two vertices: an update

This page was built for publication: On the number of alternating paths in bipartite complete graphs

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