Some relations between rank of a graph and its complement

DOI10.1016/J.LAA.2006.10.025MaRDI QIDQ869950zbMATH OpenOpenAlexFDO

Authors Alireza Alipour, Javad Ebrahimi Boroojeni, E. Ghorbani, Mirhamed Mirjalalieh Shirazi, S. Akbari

Publication date 9 March 2007

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2006.10.025

zbMATH Keywords

adjacency matrixcomplementrank

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03)

Review text

Let \(G\) be a graph of order \(n\) and rank\((G)\) denote the rank of its adjacency matrix. Clearly, \(n\leq \text{rank}(G)+\text{rank}(\overline G)\leq 2n\). In this paper we characterize all graphs \(G\) such that \(\text{rank}(G) + \text{rank}(\overline G)=n\), \(n+1\) or \(n + 2\). Also for every integer \(n \geq 5\) and any \(k\), \(0\leq k\leq n\), we construct a graph \(G\) of order \(n\), such that \(\text{rank}(G) + \text{rank}(\overline G)=n+k\).

Recommendations

• On the rank of the Doob graph and its complement
• On the graph complement conjecture for minimum rank
• Complement of a graph: a generalization
• On the complements of graphs
• scientific article; zbMATH DE number 1539538
• On vertex rankings of graphs and its relatives
• On the ranks of configurations on the complete graph
• Relationship between the rank and the matching number of a graph
• On rank of a matrix associated with graph
• On order and rank of graphs

Cites work

• A graph and its complement with specified spectral properties
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• Recent results in the theory of graph spectra
• The rank of a graph after vertex addition

Cited in

(7)

• Rank relations between a \(\{0, 1\}\)-matrix and its complement
• Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph
• Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
• A characterization of graphs with rank 5
• scientific article; zbMATH DE number 841561 (Why is no real title available?)
• On the rank of the Doob graph and its complement
• On the rank of a cograph

This page was built for publication: Some relations between rank of a graph and its complement

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