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

References

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

Files

History

  • Receive Date: 13 September 2013
  • Revise Date: 24 February 2014
  • Accept Date: 25 February 2014
  • Published Online: 01 March 2015

Share

How to cite

Statistics