The connected domination bound for connected (P_9,C_9,H)-free graphs
Statement
Let denote the path on vertices, let denote the cycle on vertices, and let be the graph shown in Figure H. A graph is -free if it contains none of these graphs as an induced subgraph. For a graph , let be its domination number and its connected domination number. Connected domination conjecture. For every connected -free graph ,
This extends the established bound for connected -free graphs; the conjecture concerns whether the same factor-two bound remains valid in the larger class obtained by forbidding , , and the graph .
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.