Questions tagged [cycles]
The cycles tag has no usage guidance.
54 questions
1
vote
0
answers
88
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
1
vote
0
answers
50
views
Computational complexity of deciding if two elements are in the same cycle of a permutation, version 2
This question has relation with this previous one, although the two cases are not likely solved with the same method.
Let us consider a function $P:\{0,1\}^*\to\{0,1\}^*$ that can be calculated in ...
- 469
5
votes
1
answer
175
views
Computational complexity of deciding if two elements are in the same cycle of a permutation
Given $n\in \mathbb{N}$, we have a bijection $P:\{0,1\}^n\to\{0,1\}^n$, i.e. $P$ is a permutation of $2^n$ symbols, $P\in S_{2^n}$. The permutation $P$ can be calculated efficiently, i.e. by a ...
- 469
2
votes
0
answers
42
views
graphs which have polynomial bounded number of cycles
How does the graph class defined as those graphs which have polynomial (or quasi polynomial) bounded number of cycles look? (in number of vertices)
I suspect it will rather non-interesting as ...
- 129
0
votes
0
answers
65
views
Cycles in Kneser graphs with three vertices forming triangles
Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...
- 2,089
2
votes
1
answer
120
views
If you have three paths from vertex x to vertex y, when are you guaranteed a cycle which contains both x and y?
Let G be an undirected, simple graph containing distinct vertices x and y. Let P,Q,R be three distinct paths in G from x to y. We can assume the graph G is only those paths (any vertex in G is in one ...
6
votes
0
answers
163
views
graphs where every cycle is a sum of triangles
I am studying a special kind of graphs, and I would like to know if they are studied in the literature and what they are called.
Let $G$ be a simple, finite, undirected, connected graph, with vertex ...
- 984
4
votes
1
answer
554
views
Construction of graphs of high girth and chromatic number
Are there any concrete constructions of graphs of both high girth and chromatic number?
Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
- 132
2
votes
1
answer
227
views
Number of endofunctions in [n] without fixed points with exactly k two-cycles
I need a (numerically) evaluable function for the number $N_{n,k}$ of endofunctions $f: [n] \rightarrow [n]$ without fixed points that have exactly $k$ two-cycles, where $[n] := \{1,\dotsc,n\}$. In ...
- 390
0
votes
0
answers
60
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?
...
- 13.9k
1
vote
0
answers
88
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 ...
- 1,547
3
votes
1
answer
162
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 ...
- 13.9k
2
votes
0
answers
733
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 ...
- 48.9k
1
vote
1
answer
313
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'}$ ...
- 13.9k
2
votes
0
answers
161
views
Abelian variety corresponding to a vector space
I would like to know what the following statement means:
"Let $B_t$ be the Abelian subvariety in $J_t$ corresponding to the $\mathbb{Q}$-vector subspace $H^1(C_t,\mathbb{Q})_{van}$ in the space $...
- 519
2
votes
2
answers
273
views
Number of edge-disjoint cycles in a holey graph
Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\...
- 20.2k
2
votes
0
answers
388
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 ...
- 21
7
votes
3
answers
395
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 ...
- 1,169
2
votes
1
answer
77
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 ...
- 13.2k
2
votes
1
answer
82
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 ...
- 13.2k
4
votes
1
answer
653
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
0
answers
137
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,389
1
vote
1
answer
341
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}
...
- 155
7
votes
1
answer
435
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
0
answers
182
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 ...
- 1,018
3
votes
1
answer
258
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 ...
- 2,251
1
vote
2
answers
205
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,389
2
votes
1
answer
735
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\...
user113393
7
votes
2
answers
435
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$-...
- 337
8
votes
4
answers
339
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 ...
- 151k
6
votes
0
answers
108
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$.
...
- 399
2
votes
0
answers
365
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 ...
- 13.9k
1
vote
1
answer
132
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\...
- 239
2
votes
2
answers
1k
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, ...
- 73
1
vote
1
answer
178
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 ...
- 197
7
votes
2
answers
8k
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 $...
- 19.1k
4
votes
2
answers
458
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 ...
- 197
4
votes
1
answer
644
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,044
2
votes
4
answers
6k
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 ...
- 121
6
votes
6
answers
33k
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 ...
- 161
7
votes
7
answers
3k
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 ...
- 6,962
3
votes
1
answer
207
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?
- 747
0
votes
0
answers
142
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,329
1
vote
2
answers
361
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 ...
- 21
4
votes
0
answers
224
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$
...
- 235
4
votes
0
answers
617
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-...
- 1,444
7
votes
3
answers
958
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?...
- 583
2
votes
2
answers
553
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 ...
- 21
0
votes
1
answer
687
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 ...
- 153
1
vote
1
answer
375
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,463