Post Your Answer
1 year ago in Combinatorial Optimization , Mathematics By Prithvi Patel
What are the recent studies on independence and covering numbers in graph products and graph powers?
I'm conducting a literature review in graph theory, specifically on combinatorial invariants. The relationships for parameters like the independence number across graph products (Cartesian, tensor, strong) and graph powers seem rich but scattered. I'm looking for a synthesis of the main recent results and open problems to identify where the field is heading.
Â
All Answers (1 Answers In All)
By Raj Shravan Answered 1 year ago
Recent research I've followed converges on a few exciting themes. There's significant work on finding exact formulas or tight bounds for the independence number of Cartesian, strong, and tensor products of specific graph families (like paths, cycles). A major direction is the computational complexity determining these numbers is often NP-hard, leading to algorithmic approximations. Another active area explores the behavior of these parameters under repeated graph powering. I would recommend looking at papers connecting these product parameters to coding theory and network design, as this is where a lot of the applied theoretical motivation is currently coming from.
Â
Reply to Raj Shravan
Related Questions