tailieunhanh - Báo cáo toán học: "Graphs with many copies of a given subgraph"

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: Graphs with many copies of a given subgraph. | Graphs with many copies of a given subgraph Vladimir Nikiforov Department of Mathematical Sciences University of Memphis Memphis TN 38152 vnikifr@ Submitted Oct 8 2007 Accepted Mar 3 2008 Published Mar 12 2008 Mathematics Subject Classification 05C35 Abstract Let c 0 and H be a fixed graph of order r. Every graph on n vertices containing at least cnr copies of H contains a blow-up of H with r 1 vertex classes of size _cr ln nJ and one vertex class of size greater than n1-cr . A similar result holds for induced copies of H . Main results Suppose that a graph G of order n contains cnr copies of a given subgraph H on r vertices. How large blow-up of H must G contain When H is an r-clique this question was answered in 3 G contains a complete r-partite graph with r 1 parts of size _cr In nJ and one part larger than n1-cr 1. The aim of this note is to answer this question for any subgraph H. First we define precisely a blow-up of a graph given a graph H of order r and positive integers x1 . xr we write H x15. xr for the graph obtained by replacing each vertex u 2 V H with a set Vu of size xu and each edge uv 2 E H with a complete bipartite graph with vertex classes Vu and Vv. Theorem 1 Let 2 r n ln n _1 r2 c 1 4 H be a graph of order r and G be a graph of order n. If G contains more than cnr copies of H then G contains a copy of H s . s t where s _c ln nJ and t nx cC . To state a similar theorem for induced subgraphs we need a proper modification of H x1 . xr we say that a graph X is of type H x1 . xr if X is obtained from H x1 . xr by adding some possibly zero edges within the sets Vu u 2 V H . Theorem 2 Let 2 r n ln n _1 r2 c 1 4 H be a graph of order r and G be a graph of order n. If G contains more than cnr induced copies of H then G contains an induced subgraph of type H s . s t where s _cr ln nJ and t n c . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N6 1 Remarks - The relations between c and n in Theorems 1 and 2 need some explanation. First for .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
crossorigin="anonymous">
Đã 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.