Strict middle-graph increase conjecture for outer-connected domination
Let be a graph of order . The strict middle-graph increase conjecture asserts that
The paper notes that this inequality holds for trees and for several standard graph families, including complete graphs, wheels, friendship graphs, complete bipartite graphs, and cycles. Whether it holds for every graph of order at least two remains open.
References
- Farshad Kazemnejad, Behnaz Pahlavsay, Elisa Palezzato and Michele Torielli, “Connected and outer-connected domination number of middle graphs”, arXiv:2206.15439 (2022).
Progress summary
A reader-submitted counterexample claims the conjecture fails for a connected eight-vertex graph, but the claim has not been independently verified.
The conjecture asks whether outer-connected domination always increases strictly when a graph is replaced by its middle graph. Kazemnejad, Pahlavsay, Palezzato, and Torielli introduced it in their paper published June 20, 2022.
Known results
- For connected of order , (Kazemnejad, Pahlavsay, Palezzato, and Torielli, 2022).
- For every tree of order , and (2022).
- The inequality was also established for several standard families, including complete graphs, wheels, friendship graphs, complete bipartite graphs, and cycles (2022).
November 7, 2026 community counterexample
A submitted argument claims that a connected graph with eight vertices and eleven edges satisfies , disproving strictness even for connected graphs. This is an unverified submission, not an established counterexample.
Current status (as of November 2026): The conjecture is proved for trees and several standard graph families, while its general validity is challenged by an unverified connected eight-vertex counterexample.
Sources
Solutions 1
A connected eight-vertex counterexample to strict increase of outer-connected domination under the middle-graph operationSee full solution
Result and scope. Kazemnejad, Pahlavsay, Palezzato and Torielli, arXiv:2206.15439, Conjecture 7.1 (γ̃c(G) < γ̃c(M(G)) for every graph of order n >= 2). False already for connected graphs: G8 (8 vertices, 11 edges) has γ̃c(G8) = 4 = γ̃c(M(G8)) under both conventions. Credit only for the connected negation; the edgeless failure is a domain artefact.
Complete proof: A connected eight-vertex counterexample to strict increase of outer-connected domination under the middle-graph operation · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.