4
$\begingroup$

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
    Take a cycle, $C_{2n+1}$.2011-04-25

1 Answers 1

1

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

  • 0
    @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.2012-12-12