无忧论文网
当前位置: 无忧论文网 > 自然科学论文 > 数学论文论文 > 数学数理论文 > 图中关于最长路和最长圈的相对长度的边极值问题
点击提交论文指导需求
高薪诚聘老师
图中关于最长路和最长圈的相对长度的边极值问题
时间:2011-01-24 浏览次数:840次 无忧论文网
点击这里在线咨询我
应用数学
图中路和圈的边极值问题图中路和圈的边极值问题
     本论文主要研究图中关于最长路和最长圈的相对长度的边极值问题。论文共分三章。
     在第一章,我们首先介绍了本文所涉及问题的基本定义、相关进展及主要结果。
     在第二章和第三章,我们研究了关于图中最长路和最长圈的相对长度的边极值问题。我们将图G中最长路和最长圈的顶点个数分别记为p(G)和c(G),定义两者的相对长度diff(G)=p(G)-c(G)。在第二章,我们证明了对于具有n个顶点的2-连通图G,其中,p(G)=p,如果p≥20并且e(G)>1/2(p-2)(n-7)+13,那么,我们有diff(G)≤1,由此推出,图G中的每一个最长圈都是一个控制圈。在p(G)=n时,我们给出图例说明所给的界是最好的。在第三章,我们证明了对于具有n个顶点的2-连通图G, 当δ(G)>3并且p(G)=n时,如果n≥41并且e(G)>1/2(n^2-13n+78),那么,我们有diff(G)≤2。我们给出图例说明所给的界是最好的。 [英文摘要]:      In this thesis, we mainly study edge-extremal problems on the relative length of the longest paths and cycles in graphs. This thesis consists of three chapters.
     In the first chapter, we introduce the background and main results of the research in the thesis.
     In the second and the third chapter, we present results on the relative length of the longest paths and cycles in graphs. For a graph G , let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle in G, respectively. Define diff(G)=p(G)-c(G), which is called the relative length of the longest paths and cycles. In the second chapter, we prove that, if G is a 2-connected graph on n vertices with p(G)=p, where p≥20, and if G has more than 1/2(p-2)(n-7)+13 edges, then diff(G)≤1, which implies that every longest cycle in G is a dominating cycle. In the third chapter, we prove that, if G is a 2-connected graph on n vertices with δ(G)>3 and p(G)=n, where n≥41, and if G has more than 1/2(n^2-13n+78) edges, then diff(G)≤2. In both cases above, the bounds on the number of edges are best possible.
     [参考文献]:     [1] P. N. Balister, E. Gyori, J. Lehel and R. H. Schelp, Connected
    graphs without long paths, Discrete Math., 308(2008), 4487-
    4494.
    [2] D. Bauer, A. Morgana, E. F. Schmeichel and H. J. Veldman,
    Long cycles in graphs with large degree sum, Discrete Math.,
    79(1989/90), 59-70.
    [3] B´ela Bollob´as, Modern Graph Theory, Springer-Verlag New
    York, 1998.
    [4] J. A. Bondy, Large cycles in graphs, Discrete Math., 1(1971),
    121-132.
    [5] J. A. Bondy, Longest paths and cycles in graphs with high
    degree, Research Report CORR 80-16, Department of Combinatorics
    and Optimization, University of Waterloo, Waterloo,
    Ontario, Canada(1980).
    [6] J. A. Bondy and S.C. Locke, Relative lengths of paths and
    cycles in 3-connected graphs, Discrete Math., 33(1981), 111-
    122.
    [7] J. A. Bondy and U.S.R. Murty, Graph Theory with Applitions,
    The Macmillan Press LTD, London, 1976.
    [8] L. Caccetta and K. Vijayan, Maximal cycle in graphs, Discrete
    Math., 98 (1991), 1-7.
    [9] G. A. Dirac, Some theorems on abstract graphs, Proc. London
    Math. Soc., 2(1952), 69-81.
    [10] H. Enomoto, J. van den Heuvel, A. Kaneko and A. Saito, Relative
    length of long paths and cycles in graphs with large degree
    sums, J. Graph Theory, 20(1995), 213-225.
    [11] P. Erd¨os and T. Gallai, On maximal paths and circuits of
    graphs, Acta Math. Acad. Sci. Hungar., 10(1959), 337-356.
    [12] R. J. Faudree and R. H. Schelp, Path Ramsey numbers in
    multicolorings, J. Combin. Theory B, 19(1975), 150-160.
    [13] Genghua Fan, Xuezheng Lv and Pei Wang, Cycles in 2-
    connected graphs, J. Combin. Theory B, 92 (2004), 379-394.
    [14] Ken-ichi Kawarabayashi, K. Ozeki and T. Yamashita, Long
    cycles in graphs without hamiltonian paths. Discrete Math.,
    308 (2008), 5899-5906.
    [15] Ken-ichi Kawarabayashi, Relative length of longest path and
    longest cycle, 6th In- ternational Conference on Graph Theory
    (Marseille, 2000), Electron. Notes Discrete Math., 5, Elsevier,
    Amsterdam, 2000.
    [16] G. N. Kopylov, On maximal paths and cycles in a graph, Soviet
    Math. Dokl., 18(1977), 593-596.
    [17] R. Li, A. Saito and R. H. Schelp, Relative length of longest
    paths and cycles in 3-connected graphs, J. Graph Theory, 37
    (2001), 137-156.
    [18] Mei Lu, Huiqing Liu and Feng Tian, Two sufficient condition
    for dominating cycles, J. Graph Theory, 49 (2005), 135-150.
    [19] Huiqing Liu, Mei Lu and Feng Tian, Relative length of longest
    paths and cycles in graphs, Graphs Combin., 23 (2007), 433-
    443.
    [20] S. C. Locke, Relative lengths of paths and cycles in k-connected
    graphs. J. Combin. Theory B, 32 (1982), 206-222.
    [21] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly
    67(1960), 55.
    [22] O. Ore, Arc coverings of graphs, Ann. Math. Pure Appl.,
    55(1961), 315-321.
    [23] K. Ozeki, M. Tsugaki and T. Yamashita, On relative length of
    longest paths and cycles. Accepted by J. Graph Theory, 2009.
    [24] D. Paulusma and K. Yoshimoto, Relative length of longest
    paths and longest cycles in a triangle-free graph, Discrete
    math., 308(2007), 1222-1229.
    [25] A. Saito, Long paths, long cycles, and their relative length, J.
    Graph Theory, 30 (1999), 91-99.
    [26] I. Schiermeyer and M. Tewes, Longest paths and longest cycles
    in graphs with large degree sums, Graphs Combin., 18 (2002),
    633-643.
    [27] D. R.Woodall, Maximal circuits of graphs, I, Acta Math. Acad.
    Sci. Hungar., 28 (1976), 77-80.
    [28] D. R. Woodall, Sufficient conditions for circuits in graphs,
    Proc. London Math. Soc., (3) 24(1972), 739-755.
    [29] D. R. Woodall, The binding number of a graph and its Anderson
    number, J. Combin. Theory B, 15(1973), 225-255.    
关于我们 | 老师招聘 | 版权声明 | 联系我们 | 付款方式 | 返回顶部 | 

COPYRIGHT ©2001 - 2013 51LUNWEN.NET. ALL RIGHTS RESERVED.
【免责声明】:本网站所提供的信息资源如有侵权、违规,请及时告知
无忧论文网提供毕业论文指导 硕士论文指导服务