Domination bound for complementary self-centered graphs

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 GSCC(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.

Sources & referencesView supporting material

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.