Pairing theorem of graph eigenvalues: Its new proof and a generalization

✍ Scribed by Mingzuo Shen

• Publisher: John Wiley and Sons
• Year: 1990
• Tongue: English
• Weight: 148 KB
• Volume: 37
• Category: Article
• ISSN: 0020-7608
• DOI: 10.1002/qua.560370203

✦ Synopsis

Abstract

Each undirected graph has its own adjacency matrix, which is real and symmetric. The negative of the adjacency matrix, also real and symmetric, is a well‐defined mathematically elementary concept. By this negative adjacency matrix, the negative of a graph can be defined. Then an orthogonal transformation can be readily found that transforms a negative of an alternant graph to that alternant graph: (−G) → G. Since the procedure does not involve the edge weights, the pairing theorem holds true for all edge‐weighted alternant graphs, including the usual “standard” graphs.