Abstract
In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K 1,k -free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C 5-free graphs, improving a recent bound given for trees.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cockayne E.J., Hedetniemi S.T., Miller D.J.: Properties of hereditary hypergraphs and middle graphs. Can. Math. Bull. 21, 461–468 (1978)
Krishnakumari B., Venkatakrishnan Y.B., Krzywkowski M.: Bounds on the vertex-edge domination number of a tree. C. R. Acad. Sci. Paris Ser. I 352, 363–366 (2014)
Lewis, J.R.: Vertex-Edge and Edge-Vertex Domination in Graphs. Ph.D. Thesis, Clemson University, Clemson (2007)
Lewis J.R., Hedetniemi S.T., Haynes T.W., Fricke G.H.: Vertex-edge domination. Util. Math. 81, 193–213 (2010)
Peters, J.W.: Theoretical and Algorithmic Results on Domination and Connectivity. Ph.D. Thesis, Clemson University, Clemson (1986)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boutrig, R., Chellali, M., Haynes, T.W. et al. Vertex-edge domination in graphs. Aequat. Math. 90, 355–366 (2016). https://doi.org/10.1007/s00010-015-0354-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00010-015-0354-2