DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 149-158
DOI: 10.7151/dmgt.1139

DESTROYING SYMMETRY BY ORIENTING EDGES: COMPLETE GRAPHS AND COMPLETE BIGRAPHS

Frank Harary

Department of Computer Science
New Mexico State University
Las Cruces, NM 88003, USA

Michael S. Jacobson

Department of Mathematics
University of Louisville
Louisville, KY 40292, USA
e-mail: mikej@louisville.edu

Dedicated to the memory of ``Uncle'' Paul Erdős who stimulated
and the research careers of many mathematicians.

Abstract

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 Ks,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.

2000 Mathematics Subject Classification: 05C25.

References

[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.

Received 21 December 1999
Revised 2 July 2001