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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (398Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (196Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
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