Pancyclic graph

Материал из WEGA

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

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

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

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

See also

  • Uniquely pancyclic graph,
  • Weakly pancyclic graph.