DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 437-456
DOI: 10.7151/dmgt.1681

Edge Dominating Sets and Vertex Covers

Ronald Dutton

Department of Computer Science
University of Central Florida,
Orlando, FL, USA

William F. Klostermeyer

School of Computing
University of North Florida
Jacksonville, FL 32224-26 USA

Abstract

Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.

Keywords: edge dominating set, matching, total dominating set, vertex cover

2010 Mathematics Subject Classification: 05C69, 05C70.

References

[1]S. Arumugam and S. Velammal, Edge Domination in Graphs, Taiwanese J. Math. 2 (1998) 173--179.
[2]G. Chatrand, L. Lesniak and P. Zhang, Graphs and Digraphs ( Chapman Hall/CRC, 2004).
[3]R. Dutton, Total vertex covers, Bull. Inst. Combin. Appl., to appear.
[4]H. Fernau and D.F. Manlove, Vertex and edge covers with clustering properties: complexity and algorithms, in: Algorithms and Complexity in Durham ACID 2006 (King's College, London, 2006) 69--84.
[5]T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, New York, 1998).
[6]W. Klostermeyer, Some questions on graph protection, Graph Theory Notes N.Y. 57 (2010) 29--33.
[7]J.R. Lewis, Vertex-edge and edge-vertex parameters in graphs, Ph.D. Disseration (Clemson University, 2007).

Received 5 January 2012
Revised 26 June 2012
Accepted 26 June 2012