×

Maximal graphs with respect to rank. (English) Zbl 1455.05032

Summary: 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 M. Lepović [Glas. Mat., III. Ser. 25(45), No. 1, 21–24 (1990; Zbl 0743.05041)], M. N. Ellingham [Australas. J. Comb. 8, 247–265 (1993; Zbl 0790.05057)], and M. Lazić [Publ. Inst. Math., Nouv. Sér. 88(102), 77–86 (2010; Zbl 1265.05383)].

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Akbari, P.J. Cameron, G.B. Khosrovshahi, Ranks and signatures of adjacency matrices, manuscript, 2004, available onlie at http://www.maths.qmu.ac.uk/lsoicher/designtheory.org/library/preprints/ranks.pdf.
[2] Bevis, J. H.; Blount, K. K.; Davis, G. J.; Domke, G. S.; Miller, V. A., The rank of a graph after vertex addition, Linear Algebra Appl., 265, 55-69 (1997) · Zbl 0884.05061
[3] Ellingham, M. N., Basic subgraphs and graph spectra, Australas. J. Combin., 8, 247-265 (1993) · Zbl 0790.05057
[4] Ghorbani, E.; Mohammadian, A.; Tayfeh-Rezaie, B., Maximum order of trees and bipartite graphs with a given rank, Discrete Math., 312, 3498-3501 (2012) · Zbl 1262.05086
[5] Ghorbani, E.; Mohammadian, A.; Tayfeh-Rezaie, B., Maximum order of triangle-free graphs with a given rank, J. Graph Theory, 79, 145-158 (2015) · Zbl 1312.05080
[6] Ghorbani, E.; Mohammadian, A.; Tayfeh-Rezaie, B., On order and rank of graphs, Combinatorica, 35, 655-668 (2015) · Zbl 1399.05147
[7] Haemers, W. H.; Peeters, M. J.P., The maximum order of adjacency matrices with a given rank, Des. Codes Cryptogr., 65, 223-232 (2012) · Zbl 1254.05102
[8] Kotlov, A.; Lovász, L., The rank and size of graphs, J. Graph Theory, 23, 185-189 (1996) · Zbl 0858.05060
[9] Lazić, M., Maximal canonical graphs with seven nonzero eigenvalues, Publ. Inst. Math. (Beograd) (N.S.), 88, 77-86 (2010) · Zbl 1265.05383
[10] Lepović, M., Maximal canonical graphs with 6 nonzero eigenvalues, Glas. Mat. Ser. III, 25, 45, 21-24 (1990) · Zbl 0743.05041
[11] B.D. McKay, Combinatorial Data, http://users.cecs.anu.edu.au/bdm/data/.
[12] Torgas̆ev, A., On infinite graphs with three and four nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts Cl. Sci. Math. Nat., 11, 39-48 (1981) · Zbl 0482.05048
[13] Torgas̆ev, A., On infinite graphs with five nonzero eigenvalues, Bull. Acad. Serbe Sci. Arts Cl. Sci. Math. Nat., 12, 31-38 (1982) · Zbl 0502.05041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.