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

Alon Noga | Zendy; Hall H. Tracy | Zendy; Knauer Christian | Zendy; Pinchasi Rom | Zendy; Yuster Raphael | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research