Ma et al.'s signature bounds conjecture for simple graphs

About 13 years old · traced to

Let GG be a simple graph with adjacency matrix A(G)A(G). Its signature is s(G)=p(G)−n(G)s(G)=p(G)-n(G), where p(G)p(G) and n(G)n(G) are respectively the numbers of positive and negative eigenvalues of A(G)A(G). Let c3(G)c_3(G) and c5(G)c_5(G) denote respectively the numbers of cycles in GG whose lengths are 4k+34k+3 and 4k+54k+5 for some integers k≥0k\geq 0. Ma et al.'s signature bounds conjecture. The inequality

−c3(G)≤s(G)≤c5(G)-c_3(G)\leq s(G)\leq c_5(G)

possibly holds for every simple graph GG. Ma et al. proved the inequality for trees, unicyclic graphs, and bicyclic graphs. This paper proves it for line graphs and power trees, while the general case is not established here.

References

Primary source

Long Wang and Yi-Zheng Fan, “The signature of line graphs and power trees”, arXiv:1310.1003 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.