INDUCED SUBGRAPH IN RANDOM REGULAR GRAPH

INDUCED SUBGRAPH IN RANDOM REGULAR GRAPH

导出

摘要 Let Gn,d be a random d-regular graph with n vertices, where d = o（n）. Given a fixed graph H, YH denotes the number of induced copies of H in Gn d In this paper, the authors determine the threshold of the event ＂YH 〉 0＂, and also obtain the induced subgraph counts inside the threshold interval.

作者 Lan XIAO Guiying YAN Yuwen WU Wei REN

机构地区 Academy of Mathematics and Systems Science

出处《Journal of Systems Science & Complexity》 SCIE EI CSCD 2008年第4期645-650,共6页 系统科学与复杂性学报（英文版）

基金 This research is supported by the National Natural Science of Foundation under Grant Nos.10531070 and 10721101 of China.

关键词 Induced subgraph Poisson distribution random regular graph strictly balanced threshold. 子图泊松分布随机规则图平衡性阈值

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献7

1J. H. Kim, B. Sudakov, and V. Vu, Small subgraphs of random regular graphs, Discrete Math., 2007, 307(15): 1961-1967.
2B. McKay and N. Wormald, Uniform generation of random regular graphs of moderate degree, J. Algorithm, 1990, 11(1): 52-67.
3B. McKay and N. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n^1/2), Ars Combinatoria, 1991, 11(4): 369-382.
4S. Janson, T. Luczak, and A. Rucifiski, Random Graphs, Wiely, New York, 2000.
5B. Bollobas, Random Graphs, Academic Press, London, 1985.
6Z. Gao and N. c. Wormald, Distribution of subgraphs of random regular graphs, Random Structures and Algorithms, 2008, 32(1): 38-48.
7N. Wormald, Models of random regular graphs, in Surveys in Combinatorics, London Mathematical Society Lecture Note Series (ed. by J. D. Lamb and D. A. Preece), 1999, Cambridge University Press, Cambridge, 1999, 239-298.

1LI WEIMIN.AN APPROACH TO CONSTRUCT AN END-REGULAR GRAPH[J].Applied Mathematics(A Journal of Chinese Universities),1998,13(2):171-178. 被引量：1
2GAO Suogang & YOU HongDepartment of Mathematics, Harbin Institute of Technology, Harbin 150001, China Correspondence should be addressed to Gao Suogang (e-mail: sggao@public.sj.he.cn).A distance regular graph of type E_1°E_d[J].Chinese Science Bulletin,2000,45(18):1656-1658. 被引量：3
3Jian-pingOu,Fu-jiZhang.Bound on m-restricted Edge Connectivity[J].Acta Mathematicae Applicatae Sinica,2003,19(3):505-510. 被引量：4
4Yun Shu GAO,Qing Song ZOU.Vertex-disjoint K_1+(K_1 ∪ K_2) in K_(1,4)-free Graphs with Minimum Degree at Least Four[J].Acta Mathematica Sinica,English Series,2014,30(4):661-674. 被引量：1
5孙志刚.A STRONG (10, 3, 4) REGULAR GRAPH[J].Chinese Science Bulletin,1983,28(3):298-300.
6施容华.SOME NOTES ON HAMILTONIAN GRAPHS[J].Chinese Science Bulletin,1987,32(14):1002-1003.
7LIU Guizhen and WANG Jianfang Department of Mathematics, Shandong University, Jinan 250100, China,Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100080, China.(a, b, k )-critical graphs[J].Chinese Science Bulletin,1997,42(17):1492-1493.
8张利民.EVERY 4-REGULAR SIMPLE GRAPH CONTAINS A 3-REGULAR SUBGRAPH[J].Chinese Science Bulletin,1986,31(9).
9刘桂真.REGULAR k-COVERED GRAPHS[J].Acta Mathematica Scientia,1989,9(2):227-230.
10李建湘.On the Factorizations of (mg, mf)-graph[J].Northeastern Mathematical Journal,2004,20(4):435-440.

Journal of Systems Science & Complexity

2008年第4期

浏览历史

内容加载中请稍等...

INDUCED SUBGRAPH IN RANDOM REGULAR GRAPH

参考文献7

相关作者

相关机构

相关主题

浏览历史