# Questions tagged [cycles]

The tag has no usage guidance.

45 questions
Filter by
Sorted by
Tagged with
45 views

### Hamming distance globally and Euclidean distance locally to a cycle

Given a permutation matrix 'the question is to decide if there is a permutation matrix representing a cycle within Hamming distance $d$ from given matrix'. Is there an efficient algorithm for it? ...
85 views

### Sequences generated from commuted quaternions and general commuted linear transformations

Given a pair of non-commuting linear transformations, $A$ and $B$, define the "next pair" in a sequence as $A*B$ and $B*A$. I am interested in finite cycles (i.e., the sequence eventually ...
119 views

### Probability permutation in turned to cycle

Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix). If you permute the columns and rows independently what is the probability resulting permutation matrix is a ...
127 views

### Expected value of length of longest cycle in permutation

Let $n$ be a positive integer and let $S_n$ be the collection of permutations $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. For $\pi\in S_n$ let $\text{maxcyc}(\pi)$ denote the length of the longest cycle ...
111 views

### Unique bipartite perfect matchings and cycles?

Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...
149 views

159 views

### A fast algorithm for deciding if a given undirected graph contains a C4 subgraph

I'm looking for an algorithm for deciding if a given undirected graph G contains C4 as a sub graph, not necessarily induced. I'm not interested in finding such a cycle, if it exists. I was told there ...
310 views

### Tree-width of graphs in which any two cycles touch

Let $G$ be a graph s.t. any two cycles $C_1, C_2 \subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph ...
69 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 ...
60 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 ...
165 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 ...
53 views

312 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 ...
164 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 ...
209 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 ...
171 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 ...
516 views

830 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, ...
### 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 ...