Premium
On graphs and algebraic graphs that do not contain cycles of length 4
Author(s) -
Alon Noga,
Hall H. Tracy,
Knauer Christian,
Pinchasi Rom,
Yuster Raphael
Publication year - 2011
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.20542
Subject(s) - combinatorics , mathematics , adjacency matrix , algebraic connectivity , discrete mathematics , adjacency list , algebraic graph theory , line graph , graph
Abstract We consider extremal problems for algebraic graphs , that is, graphs whose vertices correspond to vectors in ℝ d , where two vectors are connected by an edge according to an algebraic condition. We also derive a lower bound on the rank of the adjacency matrix of a general abstract graph using the number of 4‐cycles and a parameter which measures how close the graph is to being regular. From this, we derive a rank bound for the adjacency matrix A of any simple graph with n vertices and E edges which does not contain a copy of . © 2010 Wiley Periodicals, Inc. J Graph Theory 68:91‐102, 2011