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.

  • 6
    $\begingroup$ Take a cycle, $C_{2n+1}$. $\endgroup$ – Aryabhata Apr 25 '11 at 4:20

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

  • $\begingroup$ What is an even Hamiltonian path? $\endgroup$ – Srivatsan Jul 31 '11 at 8:11
  • $\begingroup$ @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. $\endgroup$ – Graphth Dec 12 '12 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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