Randomly n-cyclic digraphs
type: Item
instance of: scholarly article
title: Randomly n-cyclic digraphs
zbMATH Open document ID: 0577.05044
DOI: 10.1007/BF02582926
author: Gary Chartrand
author: Ortrud R. Oellermann
author: Sergio Ruiz
published in: Graphs and Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: A directed graph is called by the authors randomly n-cyclic if every directed path of length less than n can be extended to a directed cycle of length n. (The use of the adverb 'randomly' has no stochastic connotation; the conflict with the language of probabilistic combinatorics is unfortunate.) In this paper the authors show that every randomly n-cyclic directed graph has a spanning subgraph that is cyclically complete n-partite. A directed graph is cyclically complete n-partite if its vertex set is partitioned into nonempty sets \(V_ 0,...,V_{n-1}\) such that an edge joins vertex v to vertex w if and only if some i, \(v\in V_ i\) and \(w\in V_{i+1}\) (where \(V_ n\) is to be taken as \(V_ 0)\). Using this proposition they are able to characterize all randomly n-cyclic directed graphs for \(n=3,4\), and 5.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3922694
zbMATH Keywords: directed graph
zbMATH Keywords: directed path
zbMATH Keywords: directed cycle
zbMATH Keywords: randomly n-cyclic directed graph
MaRDI profile type: Publication
cites work: Q4187840
cites work: Randomly hamiltonian digraphs
cites work: Q5572939
description: scientific article; zbMATH DE number 3922694