PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

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.

 

Your Answer