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 class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$, an class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversal of a graph class="mathmlsrc">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">Gclass="mathContainer hidden">class="mathCode">$G$ is a subset class="mathmlsrc">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)class="mathContainer hidden">class="mathCode">$S\subseteq V\left(G\right)$ that intersects every subset of class="mathmlsrc">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)class="mathContainer hidden">class="mathCode">$V\left(G\right)$ that induces a subgraph isomorphic to a graph in class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$. Let class="mathmlsrc">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)class="mathContainer hidden">class="mathCode">$t_{\mathcal{F}}\left(G\right)$ be the minimum size of an class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversal of class="mathmlsrc">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">Gclass="mathContainer hidden">class="mathCode">$G$, and class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">class="imgLazyJSB inlineImage" 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">class="mathContainer hidden">class="mathCode">${\mathrm{ct}}_{\mathcal{F}}\left(G\right)$ be the minimum size of an class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversal of class="mathmlsrc">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">Gclass="mathContainer hidden">class="mathCode">$G$ that induces a connected graph. For a class of connected graphs class="mathmlsrc">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">Gclass="mathContainer hidden">class="mathCode">$\mathcal{G}$, we say that the price of connectivity of class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversals is multiplicative if, for all class="mathmlsrc">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∈Gclass="mathContainer hidden">class="mathCode">$G\in \mathcal{G}$, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si151.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=abea3767f31fb2b2ac5f3c7996634452">class="imgLazyJSB inlineImage" 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">class="mathContainer hidden">class="mathCode">${\mathrm{ct}}_{\mathcal{F}}\left(G\right)/t_{\mathcal{F}}\left(G\right)$ is bounded by a constant, and additive if class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si152.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=4fd12abe4223081764b990081b68ec59">class="imgLazyJSB inlineImage" 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">class="mathContainer hidden">class="mathCode">${\mathrm{ct}}_{\mathcal{F}}\left(G\right)-t_{\mathcal{F}}\left(G\right)$ is bounded by a constant. The price of connectivity is identical if class="mathmlsrc">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)class="mathContainer hidden">class="mathCode">$t_{\mathcal{F}}\left(G\right)$ and class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">class="imgLazyJSB inlineImage" 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">class="mathContainer hidden">class="mathCode">${\mathrm{ct}}_{\mathcal{F}}\left(G\right)$ are always equal and unbounded if class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300439&_mathId=si145.gif&_user=111111111&_pii=S0195669816300439&_rdoc=1&_issn=01956698&md5=ae7b0a86adb0226bcdeb601bfff08710">class="imgLazyJSB inlineImage" 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">class="mathContainer hidden">class="mathCode">${\mathrm{ct}}_{\mathcal{F}}\left(G\right)$ cannot be bounded in terms of class="mathmlsrc">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)class="mathContainer hidden">class="mathCode">$t_{\mathcal{F}}\left(G\right)$. We study classes of graphs characterized by one forbidden induced subgraph class="mathmlsrc">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">Hclass="mathContainer hidden">class="mathCode">$H$ and class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversals where class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$ contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected class="mathmlsrc">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">Hclass="mathContainer hidden">class="mathCode">$H$-free graphs where the price of connectivity of these class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$-transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when class="mathmlsrc">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">Fclass="mathContainer hidden">class="mathCode">$\mathcal{F}$ is the family of all cycles.