Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Günther Stiege
Title: On Periodic Graphs
Kind of Publication: Report. Berichte aus dem Department für Informatik 03/15, Universität Oldenburg, December 2015 :
Date: May 2015
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 19 English
Keywords: Periodic graphs; graph coloring
CR Classification: E.1 [Data structures] (Graphs and networks)
General Terms (ACM): Algorithms
up

Abstract

Digraphs with period p > 1 group the vertices into p disjoint classes. Any directed path traverses these classes in a fixed cyclic order. Graphs with even p are bipartite and colorable with 2 colors. Graphs with odd p are colorable with 3 colors. An efficient algorithm for finding the period in digraphs is presented. The line-simple period of an undirected biconnected block is the greatest common divisor of all line-simple closed paths in the biblock. Any period of a strongly connected complete orientation of the biblock is multiple of the line-simple period. The line-simple period may be 1 and a strongly connected complete orientation may have odd period greater 1.

Kurzfassung

In Digraphen mit Periode p > 1 werden die Knoten in disjunkte Klassen unterteilt. Jeder gerichtete Weg durchläuft diese Klassen in einer festen zyklischen Ordnung. Graphen mit geradem p sind bipartit und mit 2 Farben färbbar. Graphen mit ungeradem p sind mit 3 Farben färbbar. Es wird ein effizienter Algorithmus zum Finden der Periode eines Digraphen vorgestellt. Die linieneinfache Periode eines zweifach zusammenhängenden Blocks ist als größter gemeinsamer Teiler aller Längen geschlossener linieneinfacher Wege im Block definiert. Die Periode einer stark zusammenhängenden vollständigen Orientierun eines Biblocks ist stets ein Vielfaches der linieneinfachen Periode. Die linieneinfache Periode kann 1 sein, während eine stark zusammenhängende vollständige Orientierung eine ungerade Periode größer 1 aufweist.


Download

up

Remarks

None.
up


Last change: 2007/06/17 (Stiege)
 
a/HTML> < DIV ALIGN=right>up