Destroying symmetry by orienting edges: complete graphs and complete bigraphs
Frank Harary ; Michael S. Jacobson
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 149-158 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270313 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1139,
     author = {Frank Harary and Michael S. Jacobson},
     title = {Destroying symmetry by orienting edges: complete graphs and complete bigraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {149-158},
     zbl = {1001.05062},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1139}
}

Frank Harary; Michael S. Jacobson. Destroying symmetry by orienting edges: complete graphs and complete bigraphs. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 149-158. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1139/

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

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

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

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

[004] [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. | Zbl 0418.05050

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

[006] [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. | Zbl 0084.19304

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

[008] [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. | Zbl 0307.05115

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