Skip to main content
Name of "this paper"
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

decompose Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1n−1

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in this paperBermond and Faber - Decomposition of the complete directed graph into k-circuits (Theorem 3). However, the proof is kindakind of difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.

decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in this paper (Theorem 3). However, the proof is kinda difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.

Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the complete directed graph into k-circuits (Theorem 3). However, the proof is kind of difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.

Source Link

decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in this paper (Theorem 3). However, the proof is kinda difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.