The underlying graph of a line digraph
type: Item
instance of: scholarly article
title: The underlying graph of a line digraph
zbMATH Open document ID: 0760.05052
DOI: 10.1016/0166-218X(92)90156-5
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A restricted line digraph is the line digraph of a digraph without parallel arcs (and hence with at most one loop at any vertex) and in which each vertex has in-degree and out-degree at least two. The author shows that, apart from a few cases, any connected graph can be oriented as a restricted line digraph in at most two ways. He also characterizes the underlying graphs of restricted line digraphs and deduces from this a relation between the automorphism groups of a restricted line digraph and its underlying graph.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 94331
zbMATH Keywords: underlying graph
zbMATH Keywords: line digraph
zbMATH Keywords: automorphism groups
author: J. Villar
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: On the linegraph of a directed-graph
cites work: Large fault-tolerant interconnection networks
cites work: Q3818315
cites work: Q5834367
cites work: Maximally connected digraphs
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Some properties of line digraphs
cites work: Q3872508
cites work: Fault-tolerant routings in Kautz and de Bruijn networks
full work available at URL: 0166-218x(92)90156-5
OpenAlex ID: W2091851332
description: scientific article; zbMATH DE number 94331