Randomly n-cyclic digraphs (Q1065824): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4187840 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Randomly hamiltonian digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 19:18, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Randomly n-cyclic digraphs |
scientific article |
Statements
Randomly n-cyclic digraphs (English)
0 references
1985
0 references
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.
0 references
directed graph
0 references
directed path
0 references
directed cycle
0 references
randomly n-cyclic directed graph
0 references