On a conjecture of Lewin's problem
type: Item
instance of: scholarly article
title: On a conjecture of Lewin's problem
zbMATH Open document ID: 0972.05022
DOI: 10.1016/S0024-3795(00)00241-X
author: Bolian Liu
author: Wen Jiang
published in: Linear Algebra and its Applications
publication date: 2001-11-09T00:00:00Z
review text: Let \(l(G)\) denote the smallest \(k\) such that there exist walks from \(u\) to \(v\) of lengths \(k\) and \(k+1\) for some vertices \(u,v\) of a directed graph \(G.\) \textit{J. Shen} and \textit{S. Neufeld} [Linear Algebra Appl. 274, 411-426 (1998; Zbl 0901.05049)] conjectured that if \(G\) is a primitive directed graph nonisomorphic to the complete graph with loop at each vertex then \(\exp(G)\geq 2\cdot l(G).\) The authors of this paper prove an undirected version of the conjecture above and they characterize all primitive undirected graphs for which the identity \(\exp(G)= 2\cdot l(G)\) is attained.
reviewed by: Matúš Harminc
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1586481
zbMATH Keywords: Lewin's number
zbMATH Keywords: exponent
zbMATH Keywords: primitive graph
Wikidata QID: Q123249323
MaRDI profile type: MaRDI publication profile
cites work: On exponents of primitive matrices
cites work: On a problem of Lewin
cites work: A note on Lewin's problem
cites work: Generalized exponents of primitive symmetric digraphs
description: scientific article; zbMATH DE number 1586481