On the exponent of a primitive digraph
type: Item
instance of: scholarly article
title: On the exponent of a primitive digraph
zbMATH Open document ID: 0555.05037
DOI: 10.1016/0024-3795(85)90264-2
published in: Linear Algebra and its Applications
publication date: 1985-01-01T00:00:00Z
review text: A digraph D is primitive iff there is an integer \(k>0\) such that for all ordered pairs of vertices i,j\(\in V(D)\) there is a walk from i to j with length k. The least such k is called the exponent \(\gamma\) of the primitive digraph and satisfies \(\gamma \leq n+s(n-2)\) with n the number of vertices and s the length of the shortest elementary circuit of D. Two of the problems that are studied: Characterize the primitive digraphs on n vertices with shortest circuit length s and exponent \(n+s(n-2).\) If D is a primitive digraph on n vertices with shortest circuit length \(s\geq 2\) and exponent \(\gamma =n+s(n-2),\) does D contain an elementary circuit of length n?
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3884196
zbMATH Keywords: exponent
zbMATH Keywords: primitive digraphs
zbMATH Keywords: elementary circuit
author: Jia-Yu Shao
MaRDI profile type: Publication
full work available at URL: 0024-3795(85)90264-2
OpenAlex ID: W2079916008
cites work: Gaps in the exponent set of primitive matrices
cites work: On the Exponent of a Primitive, Nearly Reducible Matrix. II
cites work: Bounds for a Linear Diophantine Problem of Frobenius
description: scientific article; zbMATH DE number 3884196