𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the rank of a cograph

✍ Scribed by Gerard J. Chang; Liang-Hao Huang; Hong-Gwa Yeh

Book ID
104037436
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
89 KB
Volume
429
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

The rank of a graph is defined to be the rank of its adjacency matrix. Royle [G.F. Royle, The rank of a cograph, Electron. J. Combin. 10 (2003) #N11] proved a somewhat surprising result that the rank of a cograph is equal to the number of distinct non-zero rows of its adjacency matrix. In this paper we answer a question posed by Royle (2003) by giving an elementary short proof for a more general setting of this rank property of cographs.

πŸ“œ SIMILAR VOLUMES

An optimal parallel algorithm for node r
An optimal parallel algorithm for node ranking of cographs
✍ Liu Chuan-Ming; Yu Ming-Shing πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 885 KB

A ranking of a graph G is a mapping, p, from the vertices of G to the natural numbers such that for every path between any two vertices u and u, uf II, with p(u) = p(u), there exists at least one vertex w on that path with p(w) > p(u) = p(u). The value p(u) of a vertex u is the rank of vertex II. A

A good characterization of cograph contr
A good characterization of cograph contractions
✍ Le, Van Bang πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

A graph is called a cograph contraction if it is obtained from a cograph (a graph with no induced path on four vertices) by contracting some pairwise disjoint independent sets and then making the ''contracted'' vertices pairwise adjacent. Cograph contractions are perfect and generalize cographs and

The Pathwidth and Treewidth of Cographs
The Pathwidth and Treewidth of Cographs
✍ Bodlaender, Hans L.; MΓΆhring, Rolf H. πŸ“‚ Article πŸ“… 1993 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 940 KB