# Tagged Questions

The tag has no usage guidance.

66 views

### On symmetric difference of $k$-partite perfect matchings

Suppose we have a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles. Conversely when is it true that every union of even cycles comes from ...
35 views

### Minimum weight odd cycle with certain edge pairs forbidden

Given a weighted graph $G=(V,E)$ and several disjoint sets $S_1, \dots, S_t \subset E$ of edges, is there a polynomial-time algorithm to find a minimum weight odd cycle which does not contain more ...
91 views

375 views

### Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge. Note that the number of cycles in $k$-necklace is at least $2^k.$ Question : Suppose a ...
336 views

### Analytic continuation of a multiple contour integral

Let $W(t_1,\dotsc,t_n)$ a holomorphic function on some connected open set $U$ of $\mathbb C^n$. Let $\mathbf t^{(0)}$ a point of $U$. Assume that there exists a cycle $\gamma$ in $\mathbb C^m$ and a ...
1k views

### Counting simple 4-cycles in an undirected graph [closed]

I'm looking for an algorithm which just counts the number of simple and distinct 4-cycles in an undirected graph labelled with integer keys. I don't need it to be optimal because I only have to use it ...
6k views

### Calculating pisano periods for any integer

I recently stumbled across this SPOJ question: http://www.spoj.com/problems/PISANO/ The question is simple. Calculate the pisano period of a number. After I researched my way through the web, I found ...
795 views

### Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
154 views

### On cycles in self-centered graphs

Let $G$ be (connected) self-centered graph, i.e. $r(G)=d(G)=m<\infty$. My question is following Does $G$ always contains $C_{2m}$ or $C_{2m+1}$ as a subgraph?
108 views

1k views

### How many edge-disjoint cycles of length 3 are in the complete graph?

A couple of questions related to edge-disjoint cycles. Let $K_n = (V,E)$ be the complete graph on $|V|=n$ nodes. Two cycles are 'edge disjoint' if they do not share any edges. What is the size of ...
886 views

### Ramification divisor associated to a cover of a regular scheme

Let $S$ be the spectrum of $\mathbf{Z}$ or the spectrum of an algebraically closed field. (Actually, one can take $S$ to be any noetherian integral regular scheme.) Let $f:X\longrightarrow Y$ be a ...
Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (...
Hi all, If anyone has insight into the following variant of the classic problem of packing vertex-disjoint cycle into graphs I would be interested. Given a finite undirected graph $G$ embedded in ...