TAILIEUCHUNG - Báo cáo tin học: "On the Resilience of Long Cycles in Random Graphshan"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the Resilience of Long Cycles in Random Graphshan. | On the Resilience of Long Cycles in Random Graphs Domingos Dellamonica Jr Department of Mathematics and Computer Science Emory University 400 Dowman Dr. Atlanta GA 30322 USA ddellam@ Yoshiharu Kohayakaway Instituto de Matemática e Estatistica Universidade de Sao Paulo Rua do Matão 1010 05508-090 Sao Paulo Brazil yoshi@ Martin Marciniszyn Angelika Steger Institute of Theoretical Computer Science ETH Zurich 8092 Zurich Switzerland mmarcini steger @ Submitted Jun 13 2007 Accepted Feb 5 2008 Published Feb 11 2008 Mathematics Subject Classification 05C35 05C38 05C80 Abstract In this paper we determine the local and global resilience of random graphs Gn p p n-1 with respect to the property of containing a cycle of length at least 1 a n. Roughly speaking given a 0 we determine the smallest rg G a with the property that almost surely every subgraph of G Gnp having more than rg G a E G edges contains a cycle of length at least 1 a n global resilience . We also obtain for a 1 2 the smallest rI G a such that any H c G having degH v larger than rl G a degG v for all v 2 V G contains a cycle of length at least 1 a n local resilience . The results above are in fact proved in the more general setting of pseudorandom graphs. Supported by a CAPES-Fulbright scholarship. yPartially supported by FAPESP and CNPq through a Temático-ProNEx project Proc. FApEsP 2003 09925-5 and by CNPq Proc. 306334 2004-6 and 479882 2004-5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R32 1 1 Introduction Problems in extremal graph theory 1 2 usually come in the following form let P be a graph property and ụ a graph parameter determine the least m with the property that any graph G with ụ G m has P and describe the so called extremal graphs that is those G with ụ G m without P. For instance in the case of Turan s theorem P is the property of containing a clique Kt for some given t and ụ G is the number of edges e G in G. As is well known Turan s classical result .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.