Complementary Vanishing Graphs

2022/07/15 by Craig A. Erickson, Erickson, Craig, Luyining Gan +7
Computer Science · Engineering · Mathematics · #05C50 #15A18 #15B57 #65F18 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2207.07294

openalex publication_date 2022/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph G with vertices \v₁,…,v_n\, we define S(G) to be the set of symmetric matrices A=[a_i,j] such that for i≠ j we have a_i,j≠ 0 if and only if v_iv_j∈ E(G). Motivated by the Graph Complement Conjecture, we say that a graph G is complementary vanishing if there exist matrices A ∈ S(G) and B ∈ S(G) such that AB=O. We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most 8 vertices are complementary vanishing.

Related

• On the structure of self-complementary graphs
• On polyhedral graphs and their complements
• Orthogonal symmetric matrices and joins of graphs
• Eulerian graphs and local complementation
• Almost all friendly matrices have many obstructions