Maximal graphs with respect to rank

DOI10.1016/J.DISC.2020.112191MaRDI QIDQ2219972zbMATH OpenOpenAlexFDO

Authors Hossein Esmailian, S. Hossein Ghorbani, E. Ghorbani, Gholamreza Khosrovshahi

Publication date 21 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

generalized friendship graphmaximal graphmaximal treerank

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

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. A reduced graph $G$ is said to be maximal if any reduced graph containing $G$ as a proper induced subgraph has a higher rank. The main intent of this paper is to present some results on maximal graphs. First, we introduce a characterization of maximal trees (a reduced tree is a maximal tree if it is not a proper subtree of a reduced tree with the same rank). Next, we give a near-complete characterization of maximal `generalized friendship graphs.' Finally, we present an enumeration of all maximal graphs with ranks $8$ and $9$. The ranks up to $7$ were already done by Lepovi'c (1990), Ellingham (1993), and Lazi'c (2010).

Recommendations

• Maximum order of trees and bipartite graphs with a given rank
• The maximum order of adjacency matrices of graphs with a given rank
• Maximum order of triangle-free graphs with a given rank
• On order and rank of graphs
• Maximum order of graphs with a given corank

Cites work

• scientific article; zbMATH DE number 3756522 (Why is no real title available?)
• scientific article; zbMATH DE number 3790468 (Why is no real title available?)
• scientific article; zbMATH DE number 11798 (Why is no real title available?)
• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• Maximal canonical graphs with seven nonzero eigenvalues
• Maximum order of trees and bipartite graphs with a given rank
• Maximum order of triangle-free graphs with a given rank
• On order and rank of graphs
• The maximum order of adjacency matrices of graphs with a given rank
• The rank and size of graphs
• The rank of a graph after vertex addition

Cited in

(12)

• On order and rank of graphs
• Maximum order of trees and bipartite graphs with a given rank
• A characterization of long graphs of arbitrary rank
• Maximum order of graphs with a given corank
• Upper maximal graphs of posets
• Rank of Handelman hierarchy for Max-Cut
• Characterization of sub-long graphs of arbitrary rank
• A GENERALISATION OF HIGHER-RANK GRAPHS
• Optimal maximal graphs
• Maximum order of triangle-free graphs with a given rank
• Maximal generalized rank in graphical matrix spaces
• Employing star complements in search for graphs with fixed rank

This page was built for publication: Maximal graphs with respect to rank

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