The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
104 views

Cycles in Quivers and Path Algebras

I cannot find anything giving the algebra of a quiver with a single cycle on three or more vertices. In other words if your quiver consists of n vertices (n>2), and e_i is connected to e_{i+1} (taking ...
4
votes
2answers
274 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
1answer
188 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
4answers
165 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 ...
0
votes
1answer
554 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
5answers
254 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$ ...
2
votes
1answer
131 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
0answers
95 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 ...
0
votes
2answers
182 views

Ihara zeta function (graph theory) coefficients using a line graph

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
0answers
122 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
0answers
192 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
3answers
610 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 ...
1
vote
1answer
216 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
1answer
170 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
1answer
190 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 ...
1
vote
1answer
944 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 ...
4
votes
2answers
538 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 ...
0
votes
3answers
3k 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
1answer
433 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 ...