On the number of edges in a graph with no -connected subgraphs

详细信息    查看全文

• 作者：Anton Bernshteyn^a ; ^{bernsht2@illinois.edu" class="auth_mail" title="E-mail the corresponding author} ; Alexandr Kostochka^a ; ^b ; ^{kostochk@math.uiuc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Average degree ; Connectivity ; kk-connected subgraphs
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：682-688
• 全文大小：368 K

文摘

Mader proved that for n id="mmlsi2" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si2.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=36d63bb37416e07d2d0156ec551e6c98" title="Click to view the MathML source">k≥1n>n class="mathContainer hidden">n class="mathCode">n>n>n> and n id="mmlsi3" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=757364e67cffcf509a779419719018cb" title="Click to view the MathML source">n≥2kn>n class="mathContainer hidden">n class="mathCode">n>n>n>, every n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=c885fac0cfab091dd59a8e74bfb5df04" title="Click to view the MathML source">nn>n class="mathContainer hidden">n class="mathCode">$\mathrm{<font\; color="red">n</font>}$n>n>n>-vertex graph with no n id="mmlsi1" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=bdb92f8d26771b23c90805cde0323d43" title="Click to view the MathML source">(k+1)n>n class="mathContainer hidden">n class="mathCode">n>n>n>-connected subgraphs has at most n id="mmlsi6" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si6.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=0c860ab6709a92f5549b6179598736ff">nlineImage" height="25" width="108" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si6.gif"><noscript>n:bottom" width="108" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si6.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> edges. He also conjectured that for n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=c885fac0cfab091dd59a8e74bfb5df04" title="Click to view the MathML source">nn>n class="mathContainer hidden">n class="mathCode">$\mathrm{<font\; color="red">n</font>}$n>n>n> large with respect to n id="mmlsi8" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=ef79e3e741e671993d6a1471aee47597" title="Click to view the MathML source">kn>n class="mathContainer hidden">n class="mathCode">$k$n>n>n>, every such graph has at most n id="mmlsi9" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=12b03a5f4ff274ce9cdef7e954a3a709">nlineImage" height="22" width="112" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si9.gif"><noscript>n:bottom" width="112" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si9.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> edges. Yuster improved Mader’s upper bound to n id="mmlsi10" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si10.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=032a4887ea98ff3d8559ea70e8090ebd">nlineImage" height="21" width="76" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si10.gif"><noscript>n:bottom" width="76" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si10.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> for n id="mmlsi11" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si11.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=e0f6bd8c29c89d6f635e9f85a2915698">nlineImage" height="22" width="46" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si11.gif"><noscript>n:bottom" width="46" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si11.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n>. In this note, we make the next step towards Mader’s Conjecture: we improve Yuster’s bound to n id="mmlsi12" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si12.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=e5b94da324c568934c01389ecc9ae84d">nlineImage" height="21" width="70" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si12.gif"><noscript>n:bottom" width="70" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si12.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> for n id="mmlsi13" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003684&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003684&_rdoc=1&_issn=0012365X&md5=14530f6778a01413f30e7f9cc4b04030">nlineImage" height="22" width="46" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003684-si13.gif"><noscript>n:bottom" width="46" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15003684-si13.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n>.