The price of connectivity for cycle transversals

详细信息    查看全文

• 作者：Tatiana R. Hartinger^a ; ^{tatiana.hartinger@iam.upr.si" class="auth_mail" title="E-mail the corresponding author} ; Matthew Johnson^b ; ^{matthew.johnson2@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Martin Milanič^a ; ^{martin.milanic@upr.si" class="auth_mail" title="E-mail the corresponding author} ; Danië ; l Paulusma^b ; ^{daniel.paulusma@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：58
• 期：Complete
• 页码：203-224
• 全文大小：575 K

文摘

For a family of graphs n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>, an n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversal of a graph n id="mmlsi27" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si27.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=487d4e16b1091219267cc1dd33f354d4" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">$G$n>n>n> is a subset n id="mmlsi139" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si139.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=9ab7640b0c3c14009bec35735c808739" title="Click to view the MathML source">S⊆V(G)n>n class="mathContainer hidden">n class="mathCode">$S\subseteq V\left(G\right)$n>n>n> that intersects every subset of n id="mmlsi140" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si140.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ea1c4dbd06cc7b7be8ea304b4df4ae63" title="Click to view the MathML source">V(G)n>n class="mathContainer hidden">n class="mathCode">$V\left(G\right)$n>n>n> that induces a subgraph isomorphic to a graph in n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>. Let n id="mmlsi142" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si142.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=19b12ebb72bcc2d52baee1004af9ea64" title="Click to view the MathML source">t_F(G)n>n class="mathContainer hidden">n class="mathCode">n>n>n> be the minimum size of an n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversal of n id="mmlsi27" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si27.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=487d4e16b1091219267cc1dd33f354d4" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">$G$n>n>n>, and n id="mmlsi145" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">nlineImage" height="15" width="46" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300439-si145.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-S0195669816300439-si145.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> be the minimum size of an n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversal of n id="mmlsi27" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si27.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=487d4e16b1091219267cc1dd33f354d4" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">$G$n>n>n> that induces a connected graph. For a class of connected graphs n id="mmlsi148" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si148.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=144219da194008c5ccf835ff5f9ce40b" title="Click to view the MathML source">Gn>n class="mathContainer hidden">n class="mathCode">n>n>n>, we say that the price of connectivity of n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversals is multiplicative if, for all n id="mmlsi150" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si150.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=20b0dba435b879ff24ffeef1de663543" title="Click to view the MathML source">G&isin;Gn>n class="mathContainer hidden">n class="mathCode">n>n>n>, n id="mmlsi151" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si151.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=abea3767f31fb2b2ac5f3c7996634452">nlineImage" height="15" width="91" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300439-si151.gif"><noscript>n:bottom" width="91" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300439-si151.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> is bounded by a constant, and additive if n id="mmlsi152" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si152.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=4fd12abe4223081764b990081b68ec59">nlineImage" height="15" width="104" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300439-si152.gif"><noscript>n:bottom" width="104" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0195669816300439-si152.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> is bounded by a constant. The price of connectivity is identical if n id="mmlsi142" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si142.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=19b12ebb72bcc2d52baee1004af9ea64" title="Click to view the MathML source">t_F(G)n>n class="mathContainer hidden">n class="mathCode">n>n>n> and n id="mmlsi145" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">nlineImage" height="15" width="46" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300439-si145.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-S0195669816300439-si145.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> are always equal and unbounded if n id="mmlsi145" class="mathmlsrc">nce?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">nlineImage" height="15" width="46" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0195669816300439-si145.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-S0195669816300439-si145.gif">noscript>n class="mathContainer hidden">n class="mathCode">n>n>n> cannot be bounded in terms of n id="mmlsi142" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si142.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=19b12ebb72bcc2d52baee1004af9ea64" title="Click to view the MathML source">t_F(G)n>n class="mathContainer hidden">n class="mathCode">n>n>n>. We study classes of graphs characterized by one forbidden induced subgraph n id="mmlsi9" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si9.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=120b43f1c34315c12cedc7aa06db6287" title="Click to view the MathML source">Hn>n class="mathContainer hidden">n class="mathCode">$H$n>n>n> and n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversals where n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n> contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected n id="mmlsi9" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si9.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=120b43f1c34315c12cedc7aa06db6287" title="Click to view the MathML source">Hn>n class="mathContainer hidden">n class="mathCode">$H$n>n>n>-free graphs where the price of connectivity of these n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n>-transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when n id="mmlsi4" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si4.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=c686c709b0820f48160c7af18565ae55" title="Click to view the MathML source">Fn>n class="mathContainer hidden">n class="mathCode">n>n>n> is the family of all cycles.