For a connected bipartite graph with bipartition \((X,Y)\), where \(|X|= n \geq m = |Y|\geq 2\), the condition ``dist\((x,y) = 3\), \(x \in X\), \(y \in Y\) implies \(d(x) + d(y) \geq n+1\) ensures that a cycle of length \(2m\) exists. The graph is Hamiltonian if \(m=n\).
Recommendations
Cited in
(14)- Pancyclism and bipancyclism of Hamiltonian graphs
- A longest cycle version of Tutte's wheels theorem
- AN ALGORITHM FOR FINDING A MAXIMUM CYCLE OF BIPARTITE GRAPHS WITH LARGE DEGREES
- scientific article; zbMATH DE number 3875321 (Why is no real title available?)
- Determinants and Longest Cycles of Graphs
- Edge condition for long cycles in bipartite graphs
- scientific article; zbMATH DE number 3952812 (Why is no real title available?)
- scientific article; zbMATH DE number 4025473 (Why is no real title available?)
- scientific article; zbMATH DE number 4127251 (Why is no real title available?)
- Long cycles in unbalanced bipartite graphs
- Lattice graphs with non-concurrent longest cycles
- On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li
- An algorithm for finding longest cycles in certain bipartite graphs
- The ratio of the longest cycle and longest path in semicomplete multipartite digraphs
This page was built for publication: Longest cycles in certain bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380962)
