Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

DOI10.1016/J.DISC.2021.112706MaRDI QIDQ2065879zbMATH OpenOpenAlexFDO

Authors Aida Abiad, Gabriel Coutinho, B. D. Nogueira, S. Zeijlemaker, Miquel Angel Fiol

Publication date 13 January 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2010.12649

zbMATH Keywords

\(k\)-power graphchromatic numbereigenvaluesindependence number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Integer programming (90C10)

Abstract: The $k^{extth}$ power of a graph $G=(V,E)$, $G^k$, is the graph whose vertex set is $V$ and in which two distinct vertices are adjacent if and only if their distance in $G$ is at most $k$. This article proves various eigenvalue bounds for the independence number and chromatic number of $G^k$ which purely depend on the spectrum of $G$, together with a method to optimize them. Our bounds for the $k$-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.

Review text

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.

Recommendations

• Spectral bounds for the \(k\)-independence number of a graph
• Eigenvalues of the k-th power of a graph
• On the \(k\)-independence number of graphs
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• The optimal bound on the 3-independence number obtainable from a polynomial-type method

Cites work

• 2-Transitive Symmetric Designs
• A lower bound for the chromatic number of a graph
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Algebraic characterizations of distance-regular graphs
• An inertial lower bound for the chromatic number of a graph
• Coloring powers and girth
• Coloring the normalized Laplacian for oriented hypergraphs
• Computing \(k\)-independent sets for regular bipartite graphs
• CORES OF SYMMETRIC GRAPHS
• Distance colouring without one cycle length
• Eigenvalue interlacing and weight parameters of graphs
• Feasibility conditions for the existence of walk-regular graphs
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• scientific article; zbMATH DE number 5158519 (Why is no real title available?)
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 4004216 (Why is no real title available?)
• scientific article; zbMATH DE number 4045799 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 637355 (Why is no real title available?)
• scientific article; zbMATH DE number 3377258 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Independence and average distance in graphs
• Integer Programming with a Fixed Number of Variables
• Interlacing eigenvalues and graphs
• Large 2-independent sets of regular graphs
• Locally pseudo-distance-regular graphs
• Multidiameters and multiplicities
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On almost distance-regular graphs
• On the $b$ -Independence Number of Sparse Random Graphs
• On the \(k\)-independence number of graphs
• On the Shannon capacity of a graph
• Ovoids and spreads of finite classical polar spaces
• Polarities of generalized hexagons and perfect codes
• Quantum homomorphisms
• Recursive formulas for beans functions of graphs
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Spectral bounds for the \(k\)-independence number of a graph
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• The Chromatic Number of Graph Powers
• The strong chromatic index ofC4-free graphs

Cited in

(12)

• Characterizing and computing weight-equitable partitions of graphs
• On inertia and ratio type bounds for the k-independence number of a graph and their relationship
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• The optimal bound on the 3-independence number obtainable from a polynomial-type method
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• The clique number of the exact distance t-power graph: complexity and eigenvalue bounds
• Algebraic bounds for the independence and chromatic number of graph powers
• Eigenvalue bounds for the distance-t chromatic number of a graph and their application to Lee codes
• Eigenvalue bounds for the quantum chromatic number of graph powers
• On the k-independence number of graph products
• Eigenvalue bounds for distance-edge colourings

This page was built for publication: Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065879)