Questions tagged [cycles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
66 views

Name for specific cycles in graphs

Is there an established name for cycles $C\subseteq G(V,E)$ with the property that $$\lbrace u,v\rbrace\subseteq C\cap V\implies\mathrm{dist}_{|C}(u,v)\le \mathrm{dist}_{|G}(u,v)$$ I would be ...
2
votes
1answer
52 views

Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges

given a biconnected symmetric graph with weighted edges, what is the algorithmic complexity of determining a set of pairwise edge-disjoint cycles with maximal sum of edge weights if there are no other ...
3
votes
1answer
89 views

Bounding number of k-cycles in a graph

Fix any $k \geq 3$, and suppose I have a simple undirected graph $G=(V,E)$. I want a bound on the number of $k$ cycles in $G$ as a function of $|E|$. In particular, I would like to prove the following ...
2
votes
0answers
34 views

How many edges can be in an unbalanced bipartite graph of girth $>6$?

Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$. There is a simple counting argument called the Moore Bounds that gives $$|E| = O\...
1
vote
0answers
77 views

Matrix logarithm for d-dimensional cyclic permutation matrix

I want to find the matrix $\hat{H}_d$ which, when exponentiated, leads to a d-dimensional cyclic permutation transformation matrix. I have solutions for d=2: $$ \hat{U}_2 =\left( \begin{matrix} ...
7
votes
1answer
291 views

Strong tournaments

Let $T$ be a strong tournament, and let $N=v_1v_2 \cdots v_n$ be an enumeration of $V(T)$. Let $C$ be a circuit in $T$. We define $i_N(C)=|\{(v_i,v_j) \in E(C); i>j\}|$. Suppose that $N$ is chosen ...
6
votes
0answers
153 views

A question about dominating circuits in cubic graphs

Let $G$ be a 3-connected cubic graph with a dominating circuit $C$, that is, a circuit such that all edges in $G$ have at least one endvertex in $C$. Let $D$ be another circuit and let the symmetric ...
3
votes
1answer
178 views

Cycle Structure of a Permutation Based on the Binary Representation

This is a question I posted on math.stackexchange.com before but never got an answer. I am cross-posting it here. Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number ...
1
vote
2answers
150 views

Extremal density of a graph without a non-backtracking $2k$-cycle

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form $$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$ while the ...
1
vote
1answer
424 views

Pull-back of algebraic cycles

Since today is the Chow-variety day, I'm going to ask my question here. Suppose I have a smooth projective variety $X$ over a field of characteristic zero, and a smooth hyperplane $p: H\...
5
votes
2answers
188 views

Minimum covers of complete graphs by $4$-cycles

I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-...
7
votes
4answers
313 views

Iteration cycles of Z_n weights in path graphs: Why cycles of length 182 for a 6-node path?

Assign to the $n$ nodes of a path graph vertex weights forming a permutation of $(0,\ldots,n{-}1)$. Now iterate the following update repeatedly: Each node sums the weights of its neighbors, and that ...
6
votes
0answers
83 views

Localizing Bondy's metaconjecture on hamiltonicity

Definitions: Let $G$ be a graph on $n$ vertices. $G$ is Hamiltonian provided $G$ has a cycle of length $n$. $G$ is pancyclic provided $G$ has a cycle of length $\ell$ for every $3 \leq \ell \leq n$. ...
2
votes
0answers
240 views

On symmetric difference of $k$-partite perfect matchings

Given 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 symmetric ...
1
vote
1answer
119 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 $n\rightarrow\...
1
vote
2answers
610 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
1answer
138 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 ...
7
votes
2answers
4k 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
2answers
435 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
497 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
4k 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 ...
6
votes
6answers
19k 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 ...
7
votes
6answers
2k 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 $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
3
votes
1answer
177 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
113 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 \sigma(x)=\...
1
vote
2answers
332 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
0answers
212 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
577 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 edge-...
7
votes
3answers
814 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 direct?...
2
votes
2answers
407 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
481 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
283 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 ...
4
votes
1answer
2k 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 ...
6
votes
2answers
2k 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
3answers
11k 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 (...
3
votes
1answer
475 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 $...