×

On a relation between the domination number and a strongly connected bidirection of an undirected graph. (English) Zbl 1176.05058

Summary: As a generalization of directed and undirected graphs, J. Edmonds and E.L. Johnson [Combinat. Struct. Appl., Proc. Calgary internat. Conf. combinat. Struct. Appl., Calgary 1969, 69–87 (1970; Zbl 0268.05019)] 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 F. V. Fomin, M. Matamala, E. Prisner and I. Rapaport [in: Szwarcfiter, Jayme (ed.), Proceedings of the Brazilian symposium on graphs, algorithms and combinatorics, Fortaleza, Ceará, Brazil, March 17–19, 2001. Extended abstracts. Amsterdam: Elsevier, Electron. Notes Discrete Math. 7, no pag., electronic only (2001; Zbl 0981.05059)] 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory

References:

[1] Chung, F. R.K.; Garey, M. R.; Tarjan, E., Strongly connected orientations of mixed multigraphs, Networks, 15, 477-484 (1985) · Zbl 0645.90097
[2] Chvatal, V.; Thomassen, C., Distances in orientations of graphs, J. Combin. Theory, 24, 61-75 (1978) · Zbl 0311.05115
[3] Edmonds, J.; Johnson, E. L., Matching: A well-solved class of linear programs, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Combinatorial Structures and their Applications (1970), Gordon and Breach: Gordon and Breach New York), 88-92
[4] Fomin, F. V.; Matamala, M.; Prisner, E.; Rapaport, I., Bilateral orientations in graphs: Domination and AT-free classes, (Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics. Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001. Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics. Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, Electronics Notes in Discrete Mathematics, vol. 7 (2001), Elsevier Science Publishers)
[5] Robbins, H. E., A theorem on graphs with an application to a problem of traffic control, Amer. Math. Monthly, 46, 281-283 (1939) · Zbl 0021.35703
[6] Zaslavsky, T., Signed graphs, Discrete Appl. Math.. Discrete Appl. Math., Discrete Appl. Math., 5, 248-74 (1983), (erratum) · Zbl 0503.05060
[7] Zaslavsky, T., Orientation of signed graphs, Eur. J. Comb., 12, 361-375 (1991) · Zbl 0761.05095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.