# On a relation between the domination number and a strongly connected bidirection of an undirected graph

Lätsch, Martin and Peis, Britta
(2008)
*On a relation between the domination number and a strongly connected bidirection of an undirected graph.*
**Published in: **
Discrete Applied Mathematics Vol. 156 (17).
pp. 3194-3202.

## Abstract

As a generalization of directed and undirected graphs, Edmonds and Johnson introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph.

Download: |
Postscript
- Preprinted Version
Download (398Kb) | Preview |
---|---|

Download: |
PDF
- Preprinted Version
Download (196Kb) | Preview |

Export as: | |

Editorial actions: |
View Item (Login required) |

ZAIK Number: | zaik2006-515 |
---|---|

Depositing User: | Martin Lätsch |

Date Deposited: | 08 Feb 2006 00:00 |

Last Modified: | 09 Jan 2012 16:17 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/515 |