Edge Dominating Sets and Vertex Covers

Ronald Dutton; William F. Klostermeyer

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 437-456
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ronald Dutton, and William F. Klostermeyer. "Edge Dominating Sets and Vertex Covers." Discussiones Mathematicae Graph Theory 33.2 (2013): 437-456. <http://eudml.org/doc/267536>.

@article{RonaldDutton2013,
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.},
author = {Ronald Dutton, William F. Klostermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge dominating set; matching; total dominating set; vertex cover},
language = {eng},
number = {2},
pages = {437-456},
title = {Edge Dominating Sets and Vertex Covers},
url = {http://eudml.org/doc/267536},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Ronald Dutton
AU - William F. Klostermeyer
TI - Edge Dominating Sets and Vertex Covers
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 437
EP - 456
AB - 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.
LA - eng
KW - edge dominating set; matching; total dominating set; vertex cover
UR - http://eudml.org/doc/267536
ER -

References

top
  1. [1] S. Arumugam and S. Velammal, Edge Domination in Graphs, Taiwanese J. Math. 2 (1998) 173-179. Zbl0906.05032
  2. [2] G. Chatrand, L. Lesniak and P. Zhang, Graphs and Digraphs (Chapman Hall/CRC, 2004). 
  3. [3] R. Dutton, Total vertex covers, Bull. Inst. Combin. Appl., to appear. Zbl1270.05080
  4. [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. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  6. [6] W. Klostermeyer, Some questions on graph protection, Graph Theory Notes N.Y. 57 (2010) 29-33. 
  7. [7] J.R. Lewis, Vertex-edge and edge-vertex parameters in graphs, Ph.D. Disseration (Clemson University, 2007). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.