Optimal orientations of subgraphs of complete bipartite graphs

Document Type: National Conference on Labelings and Decompositions of Graphs

Authors

1 Assistant Professor Department of mathematics Annamalai University Annamalainagar 608002

2 Research Scholar, Department of Mathematics, Annamalai University, Annamalainagar 608 002

3 Mathematics Section, FEAT, Annamalai University Annamalainagar 6008002

Abstract

For a graph $G,$ let $\mathscr{D}(G)$ be the set of all strong digraphs $D$ obtained by the orientations of $G.$ The orientation number of $G$ is $\stackrel{\rightarrow}{d}\!\!(G)\,=$ min $\{d(D)\,|\,D\,\in\,\mathscr{D}(G)\},$ where $d(D)$ denotes the diameter of the digraph $D.$ In this paper‎, ‎we determine the orientation number for some subgraphs of complete bipartite graphs‎.

Keywords

Main Subjects


J‎. ‎Bang-Jensen and G‎. ‎Gutin (2009). Digraphs‎: ‎Theory‎, ‎Algorithms and Applications. Second Edition‎, ‎Springer‎, ‎London.
F‎. ‎Boesch and R‎. ‎Tindell (1980). ‎Robbins' theorem for mixed multigraphs. Amer‎. ‎Math‎. ‎Monthly. 87, 716-719
V‎. ‎Chv$acute{mbox{a}}$tal and C‎. ‎Thomassen (1978). ‎Distances in orientations of graphs. J‎. ‎Comb‎. ‎Theory. 24, 61-75
G‎. ‎Gutin (1989). ‎$m!$-sources in complete multipartite graphs‎, ‎(In Russian). Ser‎. ‎Fiz.‎- ‎Mat‎. ‎Navuk. 5, 101-106
R‎. ‎Hammack‎, ‎W‎. ‎Imrich and S‎. ‎Klav$check{mbox{z}}$ar (2011). Handbook of Product Graphs. Second Edition‎, ‎CRC Press‎, ‎New York.
K‎. ‎M‎. ‎Koh and E‎. ‎G‎. ‎Tay (2002). ‎Optimal orientations of graphs and digraphs‎: ‎a survey. Graphs and Combin.. 18, 745-756
P‎. ‎K‎. ‎Kowk‎, ‎Q‎. ‎Liu and D‎. ‎B‎. ‎West (2010). ‎Oriented diameter of graphs with diameter 3. J‎. ‎Combin‎. ‎Theory‎, ‎Ser‎. ‎B. 100, 265-274
R‎. ‎Lakshmi and P‎. ‎Paulraja (2007). ‎On optimal orientations of tensor product of complete graphs. Ars Combinatoria. 82, 337-352
R‎. ‎Lakshmi and P‎. ‎Paulraja (2009). ‎On optimal orientations of tensor product of graphs and circulant graphs. Ars Combinatoria. 92, 271-288
J‎. ‎Plesnik‎ (1985). ‎Remarks on diameters of orientations of graphs. Acta‎. ‎Math‎. ‎Univ‎. ‎Comenian.. 46/47, 225-236
H‎. ‎E‎. ‎Robbins (1939). ‎A theorem on graphs with an application to a problem of traffic control. Amer‎. ‎Math‎. ‎Monthly. 46, 281-283
L‎. ‎check{mbox{S}}$olt$acute{mbox{e}}$s (1986). ‎‎Orientations of graphs minimizing the radius or the diameter. Math‎. ‎Slovaca. 36, 289-296