Identity orientation of complete bipartite graphs |
| |
Authors: | Frank Harary Desh Ranjan |
| |
Institution: | Department of Computer Science, New Mexico State University, Las Cruces, NM 88003, USA |
| |
Abstract: | An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph Ks,t, with st, does not have an identity orientation if t3s-log3(s-1). We also show that if (r+1)(r+2)2s then Ks,3s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of Ks,t exists for 2s17. |
| |
Keywords: | Identity orientation Complete bigraphs Automorphisms |
本文献已被 ScienceDirect 等数据库收录! |
|