Destroying symmetry by orienting edges: complete graphs and complete bigraphs

Frank Harary; Michael S. Jacobson

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 2, page 149-158
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Frank Harary, and Michael S. Jacobson. "Destroying symmetry by orienting edges: complete graphs and complete bigraphs." Discussiones Mathematicae Graph Theory 21.2 (2001): 149-158. <http://eudml.org/doc/270313>.

@article{FrankHarary2001,
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 $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.},
author = {Frank Harary, Michael S. Jacobson},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {oriented graph; automorphism group; identity orientation number; identity oriented forest},
language = {eng},
number = {2},
pages = {149-158},
title = {Destroying symmetry by orienting edges: complete graphs and complete bigraphs},
url = {http://eudml.org/doc/270313},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Frank Harary
AU - Michael S. Jacobson
TI - Destroying symmetry by orienting edges: complete graphs and complete bigraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 2
SP - 149
EP - 158
AB - 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.
LA - eng
KW - oriented graph; automorphism group; identity orientation number; identity oriented forest
UR - http://eudml.org/doc/270313
ER -

References

top
  1. [1] G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman & Hall, New York, 1996). 
  2. [2] F. Harary, Graph Theory (Addison-Wesley, Reading MA 1969). 
  3. [3] F. Harary, R. Norman and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs (Wiley, New York, 1965). Zbl0139.41503
  4. [4] F. Harary and E.M. Palmer, Graphical Enumeration (Academic Press, New York, 1973). Zbl0266.05108
  5. [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. Zbl0418.05050
  6. [6] E.M. Palmer, Graphical Evolution (Wiley, New York, 1983). 
  7. [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. Zbl0084.19304
  8. [8] F. Harary and R.W. Robinson, The number of identity oriented trees (to appear). Zbl0311.05102
  9. [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. Zbl0307.05115
  10. [10] L.V. Quintas, Extrema concerning asymmetric graphs, J. Combin. Theory 5 (1968) 115-125. Zbl0157.55004

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.