Domination bound for complementary self-centered graphs

About 2 years old · traced to

Let GG be a graph of order nn. Write G‾\overline{G} for its complement, and let γ(G)\gamma(G) denote the domination number of GG. A graph is in SCC(2)SCC(2) when both GG and G‾\overline{G} are self-centered and

rad⁡(G)=diam⁡(G)=rad⁡(G‾)=diam⁡(G‾)=2.\operatorname{rad}(G)=\operatorname{diam}(G)=\operatorname{rad}(\overline{G})=\operatorname{diam}(\overline{G})=2.

Domination conjecture for SCC(2)SCC(2) graphs. If G∈SCC(2)G\in SCC(2), then

γ(G)≤⌈n⌉\gamma(G)\leq\left\lceil\sqrt{n}\right\rceil

and

γ(G‾)≤⌈n⌉.\gamma(\overline{G})\leq\left\lceil\sqrt{n}\right\rceil.

The paper introduces this conjecture for the exceptional class left after proving polynomial-time decidability outside SCC(2)SCC(2). It would give simultaneous domination-number bounds for a graph and its complement in the unresolved case.

References

Primary source

Subramanian Arumugam, Suresh Manjanath Hegde and Shashanka Kulamarva, “An improved upper bound for the domination number of a graph”, arXiv:2401.02765 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.