On graphs and algebraic graphs that do not contain cycles of length 4

Noga Alon, H. Tracy Hall, Christian Knauer, Rom Pinchasi, Raphael Yuster

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)91-102
Number of pages12
JournalJournal of Graph Theory
Volume68
Issue number2
DOIs
StatePublished - Oct 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • adjacency rank
  • algebraic graph
  • bipartite
  • forbidden subgraph
  • graph regularity
  • minimum rank
  • multiset regularity
  • square-avoiding
  • square-free

Fingerprint Dive into the research topics of 'On graphs and algebraic graphs that do not contain cycles of length 4'. Together they form a unique fingerprint.

Cite this