On 2k-twisted graphs
type: Item
instance of: scholarly article
title: On 2k-twisted graphs
zbMATH Open document ID: 0642.05026
DOI: 10.1016/S0195-6698(87)80035-5
author: Daniel Hershkowitz
author: Hans Schneider
published in: European Journal of Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: The paper is to formalize the notion of the number of twists in a chain in a directed graph and then to generalize a theorem on strongly connected graphs to graphs. A chain in a directed graph is obtained by putting a pointer at a vertex and moving it in the direction or against the direction of a connected sequence of arcs to another vertex. Each change of direction is a twist, hence the notion of a k-twisted chain. Likewise, a 2k-twisted graph is a graph such that for every pair of vertices there exists a 2k-twisted closed chain through the given vertices. It is shown that for a 2k-twisted graph the set of algebraic 2k-twisted cycles is an integral spanning set for the integral flow module of the graph. Since a graph is 0-twisted if and only if it is strongly connected, the result generalizes the well-known theorem that there is a basis for the flow space of a strongly connected graph consisting of algebraic circuits.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 4045775
zbMATH Keywords: directed graph
zbMATH Keywords: strongly connected graphs
zbMATH Keywords: twisted chain
zbMATH Keywords: twisted graph
zbMATH Keywords: twisted cycles
MaRDI profile type: Publication
cites work: Q3941433
cites work: Algorithms for Testing the Diagonal Similarity of Matrices and Related Problems
cites work: The extremal case of some matrix inequalities
cites work: Über die Determinanten mit überwiegender Hauptdiagonale
cites work: Flows on graphs applied to diagonal similarity and diagonal equivalence for matrices
full work available at URL: s0195-6698(87)80035-5
OpenAlex ID: W2109628110
description: scientific article; zbMATH DE number 4045775