# Questions tagged [cycles]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
34 views

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

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