弱弧传递图的研究
|
摘要
本文研究的是弱弧传递图的性质和结构。称图X为弱s-弧传递图，如果自同态幺半群End(X)在X的s-弧上传递作用(s≥1)。在弱点传递图和弱边传递图的研究基础上，本文讨论了弱1-弧传递图的性质，描述了弱1-弧传递图的结构，给出了顶点个数小于7的所有连通的弱1-弧传递图；本文还研究了弱1/2-传递图(即弱边传递而非弱1-弧传递的图)，得到了顶点个数最少的弱1/2-传递图，讨论了弱边传递图是弱1-弧传递图的充要条件，并给出了各种对称性之间的区别与联系；本文最后研究了图的弱s-弧传递性(s≥2)，证明了对于非二分图，弱s-弧传递性和s-弧传递性是等价的；对于二分图，弱s-弧传递性是由围长g和直径d决定的，而且还得到与s-弧传递性相一致的两个必要条件：即s存在上界(g+2)/2；当s正好达到此上界时是一个直径为g/2的二分图。
In this paper, weakly arc-transitive graphs are studied. A graph is called weakly s-arc transitive if the endomorphism monoid acts transitively on the s-arc(s>1). On the basis of weakly vertex-transitive graphs and weakly edge-transitive graphs, some properties of weakly 1-arc transitive graphs are obtained and all weakly 1-arc transitive graphs whose order is less than 7 are given; weakly 1/2-transitive graphs are also studied. A minimum weakly 1/2-transitive graph is obtained and the relationship of weakly edge-transitive graphs and weakly 1-arc transitive graphs is discussed. Moreover, weakly s-arc transitive graphs are studied. For the non-bipartite graphs, weakly s-arc transitivity is equivalent to s-arc transitivity; for the bipartite graphs, weakly s-arc transitivity depends on girth g and diameter d.
In this paper, weakly arc-transitive graphs are studied. A graph is called weakly s-arc transitive if the endomorphism monoid acts transitively on the s-arc(s>1). On the basis of weakly vertex-transitive graphs and weakly edge-transitive graphs, some properties of weakly 1-arc transitive graphs are obtained and all weakly 1-arc transitive graphs whose order is less than 7 are given; weakly 1/2-transitive graphs are also studied. A minimum weakly 1/2-transitive graph is obtained and the relationship of weakly edge-transitive graphs and weakly 1-arc transitive graphs is discussed. Moreover, weakly s-arc transitive graphs are studied. For the non-bipartite graphs, weakly s-arc transitivity is equivalent to s-arc transitivity; for the bipartite graphs, weakly s-arc transitivity depends on girth g and diameter d.
引文
[1] BIGGS N. Algebraic graph theory[M]. Cambridge: Cambridge University Press, 1993.
[2] HAHN G and Tardif C. Graph homomorphisms: structure and symmetry. In: HAHN G, SABIDUSSI G: Graph symmetry. Dordrecht: Kluwer Academic Publishers, 1996: 107-165.
[3] Godsil C and Royle G. Algebraic Graph Theory. Springer-verlag,Network. 2001.
[4] D. F. Holt. A graph which is edge transitive but not arc-transitive, J. Graph Theory, 1981, 5: 201-204.
[5] Alspach B, Marusie D and Nowitz L. Constructing graphs which are 1/2-transitive. J., Austral. Math. Soc., to appear.
[6] Knauer. U and Nieporte. M, Endomorphism of Graphs Ⅰ, The Monoid of strong Endomorphisms, Arch. Math., 1989, 52:607-614.
[7] Knauer. U, Endomorphism of Graphs Ⅱ, Various Unretractive Graphs, Arch. Math., 1990, 55: 193-203.
[8] Fan S H. Weakly symmetric graphs and their endomorphism monoids[J]. Southeast Asian Bulletin of Mathematics, 2002.
[9] Fan S H and Xie H L. Weakly transitive graphs. Journal of Algebra and Discrete Structures: 2003, 1(1):27-34.
[10] Fan S H. On End-regular bipartite graphs, Combinatorics and graph theory, Singapore: World Scientific, 1993:117-130.
[11] 谢虹玲，图的各级对称性，暨南大学研究生学报(自然科学与医学版)，2000，16(2)：1-7．
[12] YAP. H. P. Some topic in graph theory(London Math. Soc. Lecture Note Ser. 108), Cambridge University Press, 1986, first published.
[13] Ying. C and Oxley. J. on weakly symmetric graphs of order twice a prime. J. comb. theory serB, 1987, 42(2): 196-211.
[14] Marusic. D. Recent development in half-transitive graphs, disc. math.,1998,182(3): 219-231.
[15] Tutte W T. Connectivity in Graphs. Toronto University Press, 1966.
[16] I. Z. Bouwer. Vertex and edge-transitive but not 1-transitive graphs. Canad. Math. Bull., 1970, 13: 231-237.
[17] F．哈拉里，图论，上海科技出版社，1980，第一版第3次印刷：248-258．
[2] HAHN G and Tardif C. Graph homomorphisms: structure and symmetry. In: HAHN G, SABIDUSSI G: Graph symmetry. Dordrecht: Kluwer Academic Publishers, 1996: 107-165.
[3] Godsil C and Royle G. Algebraic Graph Theory. Springer-verlag,Network. 2001.
[4] D. F. Holt. A graph which is edge transitive but not arc-transitive, J. Graph Theory, 1981, 5: 201-204.
[5] Alspach B, Marusie D and Nowitz L. Constructing graphs which are 1/2-transitive. J., Austral. Math. Soc., to appear.
[6] Knauer. U and Nieporte. M, Endomorphism of Graphs Ⅰ, The Monoid of strong Endomorphisms, Arch. Math., 1989, 52:607-614.
[7] Knauer. U, Endomorphism of Graphs Ⅱ, Various Unretractive Graphs, Arch. Math., 1990, 55: 193-203.
[8] Fan S H. Weakly symmetric graphs and their endomorphism monoids[J]. Southeast Asian Bulletin of Mathematics, 2002.
[9] Fan S H and Xie H L. Weakly transitive graphs. Journal of Algebra and Discrete Structures: 2003, 1(1):27-34.
[10] Fan S H. On End-regular bipartite graphs, Combinatorics and graph theory, Singapore: World Scientific, 1993:117-130.
[11] 谢虹玲，图的各级对称性，暨南大学研究生学报(自然科学与医学版)，2000，16(2)：1-7．
[12] YAP. H. P. Some topic in graph theory(London Math. Soc. Lecture Note Ser. 108), Cambridge University Press, 1986, first published.
[13] Ying. C and Oxley. J. on weakly symmetric graphs of order twice a prime. J. comb. theory serB, 1987, 42(2): 196-211.
[14] Marusic. D. Recent development in half-transitive graphs, disc. math.,1998,182(3): 219-231.
[15] Tutte W T. Connectivity in Graphs. Toronto University Press, 1966.
[16] I. Z. Bouwer. Vertex and edge-transitive but not 1-transitive graphs. Canad. Math. Bull., 1970, 13: 231-237.
[17] F．哈拉里，图论，上海科技出版社，1980，第一版第3次印刷：248-258．