Conjecture on the induced forest number of Paley graphs of square order
Conjecture on the induced forest number of Paley graphs of square order
Let be a prime power, and let denote the Paley graph on the finite field of order . Let denote the maximum order of an induced forest in a graph . Induced forest conjecture. For a prime power,
The preceding computational searches found that adding two vertices to a maximum independent set does not produce a forest for all prime powers , suggesting that the smaller examples are anomalies. The conjecture predicts the exact maximum induced-forest order for Paley graphs of square order beyond these small cases.
Sources & referencesView supporting material
Primary source
Karen Gunderson, Karen Meagher, Joy Morris and Venkata Raghu Tej Pantangi, “Induced forests in some distance-regular graphs”, arXiv:2301.05207 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.