Ordered multiplicity inverse eigenvalue problem for graphs on six\n vertices

2017/08/08 by John Ahn, Christine Alar, Ahn, John +15
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1708.02438

openalex publication_date 2017/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a graph G, we associate a family of real symmetric matrices,\n\S(G), where for any M \∈ \S(G), the location of the\nnonzero off-diagonal entries of M are governed by the adjacency structure of\nG. The ordered multiplicity Inverse Eigenvalue Problem of a Graph (IEPG) is\nconcerned with finding all attainable ordered lists of eigenvalue\nmultiplicities for matrices in \S(G).\n For connected graphs of order six, we offer significant progress on the IEPG,\nas well as a complete solution to the ordered multiplicity IEPG. We also show\nthat while K_m,n with \min(m,n)\≥ 3 attains a particular ordered\nmultiplicity list, it cannot do so with arbitrary spectrum.\n

Related

• A zero forcing technique for bounding sums of eigenvalue multiplicities
• The inverse eigenvalue problem of a graph: Multiplicities and minors
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Graphs that allow all the eigenvalue multiplicities to be even
• The maximum multiplicity of an eigenvalue of symmetric matrices with a given graph