|
|||||
|
|
Maximum Order of Triangle‐Free Graphs with a Given Rank |
|
| Authors: | E Ghorbani A Mohammadian B Tayfeh‐Rezaie |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, K.N. TOOSI UNIVERSITY OF TECHNOLOGY, TEHRAN, IRAN;2. SCHOOL OF MATHEMATICS, INSTITUTE FOR RESEARCH IN FUNDAMENTAL SCIENCES (IPM), TEHRAN, IRAN |
| 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. |
| Keywords: | rank triangle‐free graph adjacency matrix AMS Mathematics Subject Classification (2010): 05C50 05C75 15A03 |