On a conjecture of Lewin's problem

DOI10.1016/S0024-3795(00)00241-XMaRDI QIDQ5929767zbMATH OpenWikidataFDO

Authors Bolian Liu, Wen Jiang

Publication date 9 November 2001

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(00)00241-X

zbMATH Keywords

exponentLewin's numberprimitive graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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.

Recommendations

• A note on Lewin's problem
• On a problem of Lewin
• The extremal primitive digraph with both Lewin index n-2 and girth 2 or 3.
• The proof of a conjecture on the Lewin number of primitive non-powerful signed digraphs
• The Lewin index set of primitive digraphs with order \(n\) and girth \(3\)

Cites work

• A note on Lewin's problem
• Generalized exponents of primitive symmetric digraphs
• On a problem of Lewin
• On exponents of primitive matrices

Cited in

(7)

• The proof of a conjecture on the Lewin number of primitive non-powerful signed digraphs
• On Levine-O'Sullivan's sequence and its conjecture
• A weaker form of Ulam's conjecture
• On Lee's conjecture and some results
• scientific article; zbMATH DE number 3679918 (Why is no real title available?)
• On a conjecture of Lemke and Kleitman
• A note on Lewin's problem

This page was built for publication: On a conjecture of Lewin's problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5929767)