On a relation between the domination number and a strongly connected bidirection of an undirected graph
Lätsch, Martin and Peis, Britta
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.
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.
|Depositing User:||Martin Lätsch|
|Date Deposited:||08 Feb 2006 00:00|
|Last Modified:||09 Jan 2012 16:17|