Longest cycles in certain bipartite graphs
Let G be a connected bipartite graph with bipartition (X,Y) such that |X|≥|Y|(≥2), n=|X| and m=|Y|. Suppose, for all vertices x∈X and y∈Y, dist(x,y)=3 implies d(x)+d(y)≥n+1. Then G contains a cycle of length 2m. In particular, if m=n, then G is hamiltomian.
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1998-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171298000131 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|