✦ LIBER ✦

The rank and size of graphs

✍ Scribed by Kotlov, Andrew; Lov�sz, L�szl�

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 254 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199610)23:2<185::aid-jgt9>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the number of points with pairwise different sets of neighbors in a graph is 0(2'/2), where T is the rank of the adjacency matrix. We also give an example that achieves this bound.

📜 SIMILAR VOLUMES

Rank-width of random graphs

✍ Choongbum Lee; Joonkyung Lee; Sang-il Oum 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour [J Combin Theory Ser B 96 (2006), 514-528]. We investigate the asymptotic behavior of rank-width of a random graph G(n, p). We show that, asymptotically almost surely, (i 2 ), then rw(G(n, p)) =

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆

Chromatic Number and the 2-Rank of a Gra

Chromatic Number and the 2-Rank of a Graph

✍ C.D. Godsil; Gordon F. Royle 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We show that if the adjacency matrix of a graph X has 2-rank 2r, then the chromatic number of X is at most 2 r +1, and that this bound is tight. 2001

The size of strength-maximal graphs

✍ Hong-Jian Lai 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB

## Abstract Let __G__ be a graph and let __k__′(__G__) be the edge‐connectivity of __G__. The __strength__ of __G__, denoted by k̄′(__G__), is the maximum value of __k__′(__H__), where __H__ runs over all subgraphs of __G__. A simple graph __G__ is called k‐__maximal__ if k̄′(__G__) ≤ __k__ but for

Real flow number and the cycle rank of a

Real flow number and the cycle rank of a graph

✍ Robert Lukot'ka; Martin Škoviera 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number __p__/__q__ + 1, where __p__ and __q__ are two relatively prime numbers must have cycle rank at least __p__ + __q__ − 1. A

Face Size and the Maximum Genus of a Gra

Face Size and the Maximum Genus of a Graph 1. Simple Graphs

✍ Yuanqiu Huang; Yanpei Liu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 150 KB

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and S8 koviera (1990, in ``Topics in Combinatorics and Graph Theory,'' pp.