Premium
Lower bounds on the number of triangles in a graph
Author(s) -
Fisher David C.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130411
Subject(s) - combinatorics , mathematics , graph , upper and lower bounds , spectral radius , complement (music) , eigenvalues and eigenvectors , physics , mathematical analysis , phenotype , biochemistry , chemistry , quantum mechanics , complementation , gene
For a simple graph G , let f ( z ) ≡ 1 − c 1 z + c 3 z 2 − c 3 z 3 + … where c k is the number of complete subgraphs on k nodes in G . Let r ( G ) be the reciprocal of the smallest real root of f ( z ). Let λ( Ḡ ) be the spectral radius of the complement of G . We show r ( G ) ⩾ λ( Ḡ ) + 1. This is used to show that if c 2 1 /4 ⩽ c 2 ⩽ c 2 1 /3, then a lower bound on the number of triangles in G is c 3 ⩾ [9 c 2 c 1 − 2 c 2 1 − 2( c 2 1 − 3 c 2 ) 3/2 ]/27. This improves a bound of Bollobás and is asymptotically sharp. Also, this paper shows that(a corollary of a result from Erdös and Hanini) and the average number of triangles in a graph with c 1 nodes and c 2 edges is E ( c 3 ) = 3/4( C 2 2 − 3 c 2 + 2) c 2 /( c 3 1 − 5 c 1 − 4). These are graphically compared to the best known lower bounds.