The cycles tag has no usage guidance.

**0**

votes

**0**answers

73 views

### Perfect matchings that never combine to form cycle union cover

Can there be exponential number (in terms of vertices) of perfect matchings on a bipartite graph so that no combination of them yields a union of cycles that cover all vertices?
Is there a way to ...

**0**

votes

**0**answers

55 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 ...

**0**

votes

**0**answers

34 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 ...

**1**

vote

**1**answer

89 views

### Probability of having no cycles of fixed length in $d$-regular graphs

According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as ...

**0**

votes

**0**answers

150 views

### Cycle class map in smooth quasi-projective varieties

Let $X$ be a smooth quasi-projective variety over $\mathbb{C}$ and $Z$ be a closed subvariety of codimension $k$.
Q1. How to define a cycle class $[Z]\in H^k(X,\Omega_X^{k})$ ?
Q2. More general, ...

**1**

vote

**1**answer

112 views

### Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...

**5**

votes

**2**answers

823 views

### How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...

**4**

votes

**2**answers

371 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 ...

**4**

votes

**1**answer

327 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 ...

**1**

vote

**4**answers

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

**2**

votes

**2**answers

4k 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 ...

**5**

votes

**6**answers

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

**3**

votes

**1**answer

150 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?

**0**

votes

**0**answers

106 views

### Notation for substructure, especially for permutations?

Is there a standard notation that expresses substructure?
The specific case that I care about is the following:
Suppose $\sigma,\tau$ are permutations such that $$\sigma(x)\not=x\implies ...

**1**

vote

**2**answers

247 views

### Ihara zeta function (graph theory) coefficients using a line graph [closed]

I'VE COMPLETELY REVISED MY QUESTION
I wish to take a simple undirected graph (i.e. the complete graph K_4)
Arbitrarily direct said graph, and then create a line graph from the directed version of ...

**4**

votes

**0**answers

151 views

### Reciprocity Map and Cycle Class Map

This might be a very naive question but here it goes. Let X be a smooth variety of dimension d over a p-adic field. We have the n part of the rerciprocity map:
$rec/n: SK_1(X)/n \to \pi^{ab}_1(X)/n$
...

**4**

votes

**0**answers

364 views

### Expected number of components with multiple cycles in a subgraph of a square lattice

Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the ...

**6**

votes

**3**answers

660 views

### 2-cycle of K3 surface

Hi there,
I want to ask about the 2-cycle of K3 surface.
As we know, its betti number $b_2$=22, so there will be 22 2-cycle generators.
Is there any topological way to figure out such cycles ...

**2**

votes

**2**answers

308 views

### Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...

**0**

votes

**1**answer

295 views

### finding missing edge in DAG which, when added, would create the longest cycle

Hey all,
Not sure if this is a math problem or an algorithm problem - but hoping it has a math style answer.
If I have a directed graph I can find all the closed loops - easy. (Actually not at all ...

**1**

vote

**1**answer

213 views

### Definition of convex cycles

Consider the following definition.
Let $C$ be a cycle of a simple graph $G$. We say that $C$ is convex if for any pair of distinct vertices $u,v \in V(C)$ $$ d_C(u,v) < d_{G-C}(u,v).$$
Is there ...

**3**

votes

**1**answer

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

**5**

votes

**2**answers

818 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 ...

**1**

vote

**3**answers

5k views

### Cycle of length 4 in an undirected graph

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

**2**

votes

**1**answer

452 views

### Compute number vertex disjoint cycles in graph surrounding a face

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