1. Maximal graphs with respect to rank
- Author
-
Esmailian, H., Ghorbani, E., Ghorban, S. Hossein, and Khosrovshahi, G. B.
- Subjects
Mathematics - Combinatorics ,05C50, 05C05, 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. 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)., Comment: 18 pages, final version, to appear in Discrete Mathematics
- Published
- 2019