Maximum order of triangle-free graphs with a given rank

DOI10.1002/JGT.21822MaRDI QIDQ5251207zbMATH OpenOpenAlexFDO

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

Publication date 22 May 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

ranktriangle-free graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Vector spaces, linear dependence, rank, lineability (15A03)

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. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.

Recommendations

• Maximum order of trees and bipartite graphs with a given rank
• A characterization of graphs with rank 5
• Maximal graphs with respect to rank
• On order and rank of graphs
• Maximum order of graphs with a given corank

Cites work

• Fundamentals of Error-Correcting Codes
• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• Maximum order of trees and bipartite graphs with a given rank
• 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

(9)

• On order and rank of graphs
• Maximum order of trees and bipartite graphs with a given rank
• Maximum order of graphs with a given corank
• Maximal graphs with respect to rank
• A finite non-unit free triangle order
• scientific article; zbMATH DE number 5914876 (Why is no real title available?)
• The rank and size of graphs
• A discrete variation of the Littlewood-Offord problem
• 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 triangle-free graphs with a given rank

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