✦ LIBER ✦

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

✍ Scribed by Noga Alon; H. Tracy Hall; Christian Knauer; Rom Pinchasi; Raphael Yuster

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 130 KB
Volume: 68
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20542

No coin nor oath required. For personal study only.

✦ Synopsis

We consider extremal problems for algebraic graphs, that is, graphs whose vertices correspond to vectors in R 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 K 2,r : rank(A) ≥ (E -2n(r +1)) / (r 2 √ n). ᭧ 2010

📜 SIMILAR VOLUMES

A characterization of well-covered graph

A characterization of well-covered graphs that contain neither 4- nor 5-cycles

✍ A. Finbow; B. Hartnell; R. J. Nowakowski 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 434 KB 👁 1 views

## Abstract A graph is well covered if every maximal independent set has the same cardinality. A vertex __x__, in a well‐covered graph __G__, is called extendable if __G – {x}__ is well covered and β(__G__) = β(__G – {x}__). If __G__ is a connected, well‐covered graph containing no 4‐ nor 5‐cycles

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥