Equal-component failure-state conjecture for proportional edge connectivity
Statement
Let denote the class of graphs with vertices and edges. For , let be a multiple of , and let and denote the proportional edge connectivity of a graph and the maximum such value over , respectively. A failure state is the graph obtained after removing an edge disconnecting set.
Equal-component failure-state conjecture. There exists such that
and the failure state of can be written as the union of components of order .
The conjecture is intended to describe the structure of an extremal failure state and is used to seek upper bounds through bipartite subgraphs of graph complements. The source gives no resolution, so its status remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.