Characterization of graphs for which the blow-up optimization is unattained
Characterization of graphs for which the blow-up optimization is unattained
Let be a graph with no isolated vertices, let be a positive integer, and let be the optimization parameter defined in the paper. Attainment conjecture for . The quantity is not achieved if and only if and either or for some , where is the matching on edges.
The paper notes that the two listed families are known never to attain the optimum, whereas is attained whenever . The conjecture proposes that these are the only exceptions.
Sources & referencesView supporting material
Primary source
Christopher Cox and Ryan R. Martin, “Counting paths, cycles and blow-ups in planar graphs”, arXiv:2101.05911 (2022).
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.