Maximum order of trees and bipartite graphs with a given rank

DOI10.1016/J.DISC.2012.07.040MaRDI QIDQ1759390zbMATH OpenOpenAlexFDO

Authors E. Ghorbani, B. Tayfeh-Rezaie, A. Mohammadian

Publication date 20 November 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3060

zbMATH Keywords

adjacency matrixbipartite graphsreduced graphstree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. Akbari, Cameron, and Khosrovshahi conjectured that the number of vertices of every reduced graph of rank r is at most $m(r)=2^{(r+2)/2}-2$ if r is even and $m(r)=5cdot{2}^{(r-3)/2}-2$ if r is odd. In this article, we prove that if the conjecture is not true, then there would be a counterexample of rank at most $46$. We also show that every reduced graph of rank r has at most $8m(r)+14$ vertices.

Review text

A graph is called reduced if there exist no isolated vertices and no vertices with the same neighbourhood. The rank of a graph \(G\) is the rank of its adjacency matrix. The authors prove that every reduced tree of rank \(r\) has at most \(r/2-1\) vertices and that every reduced bipartite of rank \(r\) has at most \(2^{r/2} + r/2 -1\) vertices. They give also characterisations of the classes of graphs which achieve the bounds.

Recommendations

• Maximum order of triangle-free graphs with a given rank
• Maximal graphs with respect to rank
• Maximum order of graphs with a given corank
• On order and rank of graphs
• scientific article; zbMATH DE number 6100973

Cites work

• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• ON THE MULTIPLICITIES OF GRAPH EIGENVALUES
• Rank and chromatic number of a graph
• The maximum order of adjacency matrices of graphs with a given rank
• The rank and size of graphs
• The rank of a cograph

Cited in

(12)

• On order and rank of graphs
• Maximum order of graphs with a given corank
• Maximal graphs with respect to rank
• Real symmetric matrices and their negative eigenvalues
• The maximum order of reduced square (0,1)-matrices with a given rank
• Two trees in maximal planar bipartite graphs
• scientific article; zbMATH DE number 2170465 (Why is no real title available?)
• scientific article; zbMATH DE number 798644 (Why is no real title available?)
• Maximum order of triangle-free graphs with a given rank
• A discrete variation of the Littlewood-Offord problem
• The maximum order of adjacency matrices of graphs with a given rank
• Existence of a non-zero (0, 1)-vector in the row space of adjacency matrices of simple graphs

This page was built for publication: Maximum order of trees and bipartite graphs with a given rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759390)