# Pancyclic graph

Перейти к навигации Перейти к поиску

Pancyclic graph --- панциклический граф.

A graph $\displaystyle{ G }$ on $\displaystyle{ n }$ vertices is said to be a pancyclic graph if it contains cycles on every length from 3 to $\displaystyle{ n }$.

A graph $\displaystyle{ G }$ of order $\displaystyle{ n }$ is said to be $\displaystyle{ [a,b] }$-pancyclic, if for every integer $\displaystyle{ i }$ ($\displaystyle{ a \leq i \leq b }$) there exists a cycle $\displaystyle{ C_{i} }$ of length $\displaystyle{ i }$ in $\displaystyle{ G }$. Similarly, $\displaystyle{ G }$ is said to be $\displaystyle{ [a,b] }$-vertex-pancyclic (resp. $\displaystyle{ [a,b] }$-edge-pancyclic), if for every vertex $\displaystyle{ v }$ (resp. edge $\displaystyle{ e }$) and every $\displaystyle{ i }$ there is a cycle $\displaystyle{ C_{i} }$ containing $\displaystyle{ v }$ (resp. $\displaystyle{ e }$). $\displaystyle{ G }$ is said to be $\displaystyle{ [a,b] }$-panconnected, if for every pair of distinct vertices $\displaystyle{ u,v }$ and every $\displaystyle{ i }$ there exists a path $\displaystyle{ P_{i}[u,v] }$ of $\displaystyle{ i }$ vertices connecting $\displaystyle{ u }$ and $\displaystyle{ v }$.

Obviously, if $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-panconnected, then $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-edge-pancyclic; if $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-edge-pancyclic, then $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-vertex-pancyclic and if $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-vertex-pancyclic, then $\displaystyle{ G }$ is $\displaystyle{ [a,b] }$-pancyclic.

## See also

• Uniquely pancyclic graph,
• Weakly pancyclic graph.