Geodesic
Destroying symmetry by orienting edges: complete graphs and complete bigraphs
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 149-158 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Our purpose is to introduce the concept of determining the smallest number of edges of a graph which can be oriented so that the resulting mixed graph has the trivial automorphism group. We find that this number for complete graphs is related to the number of identity oriented trees. For complete bipartite graphs K_s,t, s ≤ t, this number does not always exist. We determine for s ≤ 4 the values of t for which this number does exist.
Keywords: oriented graph, automorphism group 
@article{DMGT_2001_21_2_a0,
     author = {Harary, Frank and Jacobson, Michael},
     title = {Destroying symmetry by orienting edges: complete graphs and complete bigraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {149--158},
     year = {2001},
     volume = {21},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a0/}
}
TY  - JOUR
AU  - Harary, Frank
AU  - Jacobson, Michael
TI  - Destroying symmetry by orienting edges: complete graphs and complete bigraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 149
EP  - 158
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a0/
LA  - en
ID  - DMGT_2001_21_2_a0
ER  - 
%0 Journal Article
%A Harary, Frank
%A Jacobson, Michael
%T Destroying symmetry by orienting edges: complete graphs and complete bigraphs
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 149-158
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a0/
%G en
%F DMGT_2001_21_2_a0
Harary, Frank; Jacobson, Michael. Destroying symmetry by orienting edges: complete graphs and complete bigraphs. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 149-158. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a0/

[1] G. Chartrand and L. Lesniak, Graphs Digraphs, third edition (Chapman Hall, New York, 1996).

[2] F. Harary, Graph Theory (Addison-Wesley, Reading MA 1969).

[3] F. Harary, R. Norman and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs (Wiley, New York, 1965).

[4] F. Harary and E.M. Palmer, Graphical Enumeration (Academic Press, New York, 1973).

[5] A. Blass and F. Harary, Properties of almost all graphs and complexes, J. Graph Theory 3 (1979) 225-240, doi: 10.1002/jgt.3190030305.

[6] E.M. Palmer, Graphical Evolution (Wiley, New York, 1983).

[7] F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math. 101 (1959) 141-162, doi: 10.1007/BF02559543.

[8] F. Harary and R.W. Robinson, The number of identity oriented trees (to appear).

[9] D.J. McCarthy and L.V. Quintas, A stability theorem for minimum edge graphs with given abstract automorphism group, Trans. Amer. Math. Soc. 208 (1977) 27-39, doi: 10.1090/S0002-9947-1975-0369148-4.

[10] L.V. Quintas, Extrema concerning asymmetric graphs, J. Combin. Theory 5 (1968) 115-125.