A diameter bound on the exponent of a primitive directed graph
type: Item
instance of: scholarly article
title: A diameter bound on the exponent of a primitive directed graph
zbMATH Open document ID: 0860.05038
DOI: 10.1016/0024-3795(94)00203-7
author: Stewart W. Neufeld
published in: Linear Algebra and its Applications
publication date: 1996-11-25T00:00:00Z
review text: A directed graph \(G\) is primitive if there exists a positive integer \(k\) such that for every pair of vertices \(u,v\in G\) there is a walk from \(u\) to \(v\) of length \(k\). The least such \(k\) is called the exponent of \(G\). We define \(G^k\) to be the directed graph having the same vertex set as \(G\) and arcs \((u,v)\) if and only if there is a walk in \(G\) of length \(k\) from vertex \(u\) to vertex \(v\). A well-known upper bound for the exponent of a primitive directed graph \(G\) of order \(n\) is \((n-1)^2+1\), due to H. Wielandt in 1950. Our main result is the following refinement of the Wielandt bound: If \(G\) is a primitive directed graph with diameter \(d\), then the exponent of \(G\) is at most \(d^2+1\). We construct the primitive graphs for which equality is attained and we generalize the bound to the class of irreducible matrices. In the course of proving the main result we find the following which is interesting in its own right: If \(G\) is a primitive directed graph with diameter \(d\), then the diameter of \(G^k\) is at most \(d\) for all positive integers \(k\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 931918
zbMATH Keywords: Boolean matrices
zbMATH Keywords: directed graph
zbMATH Keywords: walk
zbMATH Keywords: exponent
zbMATH Keywords: diameter
zbMATH Keywords: primitive graphs
zbMATH Keywords: irreducible matrices
MaRDI profile type: Publication
full work available at URL: 0024-3795(94)00203-7
OpenAlex ID: W2030741686
cites work: Q4190651
cites work: Gaps in the exponent set of primitive matrices
cites work: A bound on the exponent of a primitive matrix using Boolean rank
cites work: Bounds on the exponent of primitivity which depend on the spectrum and the minimal polynomial
cites work: The index of primitivity of a non-negative matrix
cites work: On Powers of Non-Negative Matrices
cites work: On exponents of primitive matrices
cites work: On the Number of Positive Entries in the Powers of a Non-Negative Matrix
cites work: Proof of a conjecture about the exponent of primitive matrices
cites work: Bounds for a Linear Diophantine Problem of Frobenius, II
cites work: Bounds for a Linear Diophantine Problem of Frobenius
cites work: Unzerlegbare, nicht negative Matrizen
description: scientific article; zbMATH DE number 931918