Optimization of eigenvalue bounds for the independence and chromatic number of graph powers (Q2065879): Difference between revisions

Given a graph \(G = (V,E)\), the \(k\)th power of \(G\), denoted by \(G^k\), is the graph with \(V\) as the vertex set and two vertices are adjacent if and only if their distance in \(G\) is at most \(k\). Using the spectrum of \(G\) together with a method of integer programming to optimize them, this article proves several eigenvalue bounds for the independence number and chromatic number for the power graph \(G^k\). Consequently, the work presented in this article is related to some previously known bounds in the literature. Moreover, sharp bounds for some infinite families of graphs are presented as well. The article handles a particular case where the relation between the spectrums of \(G\) and \(G^k\) is known. Moreover, the general case of unknown relation between the spectrums of \(G\) and \(G^k\) is considered as well. Open problems are given and some strategies on how to attack these problems are suggested for further consideration.