Proof of a conjecture involving the second largest D-eigenvalue and the number of triangles

摘要

Let G be a connected graph of order n with tr triangles and D be the distance matrix of G. Let lambda(1)(D) >= lambda(2)(D) >= ... >= lambda(n)(D) be the D-eigenvalue of the graph G. Fajtlowicz (1998) [4] conjectured that lambda(2) (D) <= tr when the independent number alpha(G) <= 2. In this paper, the conjecture is confirmed and the extremal graph when the equality holds is characterized. (C) 2015 Elsevier Inc. All rights reserved.