A note on the domination number in bipartite graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Author

Department of Mathematics, Shahed University, Tehran, Iran

Abstract

‎Archdeacon et al. [J. Graph Theory 46 (2004), 207--210] proved that if $G$ is a bipartite graph with partite sets $X$ and $Y$ whose vertices in $Y$ are of minimum degree at least $3$ then there exists a set $A\subseteq X$ of size at most
$\frac{|X\cup Y|}{4}$ such that every vertex in $Y$ is adjacent to a vertex in $A$. We generalize this result for all bipartite graphs with minimum degree $\delta\geq 3$ using the Brooks Theorem on the vertex coloring.

Keywords

Main Subjects

References

[1] D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004), no. 3, 207–210. https://doi.org/10.1002/jgt.20000
[2] R.L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941), no. 2, 194–197.
[3] T. Gerlach and J. Harant, A note on domination in bipartite graphs, Discuss. Math. Graph Theory 22 (2002), no. 2, 229–231. https://doi.org/10.7151/dmgt.1171
[4] J. Harant and A. Pruchnewski, A note on the domination number of a bipartite graph, Ann. Comb. 5 (2001), no. 2, 175–178.
[5] J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009), no. 1, 113–122. https://doi.org/10.1016/j.disc.2007.12.051
[6] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in domination in graphs, 2020.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, 1998.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 April 2026

Files

Share

How to cite

Statistics