On completely positive graphs and their complements
| Autor: | Felix Goldberg |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
Strongly regular graph Numerical Analysis Algebra and Number Theory Symmetric graph Completely positive matrices Completely positive graphs Distance-regular graph Combinatorics Graph energy Graph power Nordhaus–Gaddum type theorems Discrete Mathematics and Combinatorics Graph homomorphism Split graph Geometry and Topology Spectral radius Complement graph Mathematics |
| Zdroj: | Linear Algebra and its Applications. :45-51 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/S0024-3795(03)00419-1 |
| Popis: | In this paper we establish two results concerning completely positive graphs and their complements: (1) the complement of a completely positive graph on n ⩾9 vertices is not completely positive; (2) the spectral radius of the adjacency matrix of a completely positive graph on n ⩾6 vertices is at most 3 8 n . We show that (1) is best possible without additional assumptions. The proofs of (1) and (2) rely on a known fact of extremal graph theory which we state in the language of completely positive graphs and furnish with a proof: the size of a completely positive graph on n ⩾6 vertices is at most ⌊ n 2 /4⌋. We also give another short proof of (1), under the additional assumption that n ⩾17. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|