PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 149-158
Tytuł artykułu

Destroying symmetry by orienting edges: complete graphs and complete bigraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
21
Numer
2
Strony
149-158
Opis fizyczny
Daty
wydano
2001
otrzymano
1999-12-21
poprawiono
2001-07-02
Twórcy
autor
  • Department of Computer Science, New Mexico State University, Las Cruces, NM 88003, USA
  • Department of Mathematics, University of Louisville, Louisville, KY 40292, USA
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1139
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.