Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G = (V, E)$ be a connected, undirected, and non-bipartite graph. What is the maximum length of the shortest odd cycle?

I'm working on an algorithm for computing bipartivity degree. See, for example, section 7.2 of Characterization of Complex Networks: A Survey of measurements. My algorithm is similar in some ways to subgraph centrality, but it's not a spectral algorithm; that is, it's not expressed in terms of the eigenvalues or eigenvectors of the adjacency matrix of the graph. Instead, I find certain kinds of closed walks of length $1 \ldots k$. So, if there's an known upper bound on the length of the shortest odd cycle in a non-bipartite graph, then I can know how large $k$ must be in order to capture some information about how far from being bipartite a non-bipartite graph is.

share|improve this question
6  
Take a cycle, $C_{2n+1}$. –  Aryabhata Apr 25 '11 at 4:20
add comment

1 Answer

This problem might be NP-Hard, since it's similar to finding the longest even Hamiltonian path, $p = (v \rightarrow w)$ , in $G$ s.t. $e = (v,w) \in E(G)$.

share|improve this answer
    
What is an even Hamiltonian path? –  Srivatsan Jul 31 '11 at 8:11
    
@Srivatsan As in, do we use vertices or edges? Is that your quetion? Surely, from the context, he is talking about the edges. And, since length of paths are usually defined in terms of edges, there doesn't seem to be any confusion. –  Graphth Dec 12 '12 at 18:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.