-dominating -trees of graphs

详细信息    查看全文

• 作者：Mikio Kano^a ; ^{mikio.kano.math@vc.ibaraki.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Kenta Ozeki^b ; ^c ; ^{ozeki@nii.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Masao Tsugaki^d ; ^{tsugaki@hotmail.com" class="auth_mail" title="E-mail the corresponding author} ; Guiying Yan^e ; ^{yangy@amss.ac.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：kk-tree ; Dominating tree ; nn-connected graph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：729-736
• 全文大小：437 K

文摘

Let an id="mmlsi6" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si6.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=a011faf9aa565fdd55b8a57622d12c71" title="Click to view the MathML source">k≥2an>an class="mathContainer hidden">an class="mathCode">ath altimg="si6.gif" overflow="scroll">k≥2ath>an>an>an>, an id="mmlsi7" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si7.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=968b3a8d7e9523bab9b6a10b823e3940" title="Click to view the MathML source">l≥2an>an class="mathContainer hidden">an class="mathCode">ath altimg="si7.gif" overflow="scroll">l≥2ath>an>an>an>, an id="mmlsi8" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si8.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=c1212466d81c8ed1b0e80b7e9d1cc1db" title="Click to view the MathML source">m≥0an>an class="mathContainer hidden">an class="mathCode">ath altimg="si8.gif" overflow="scroll">m≥0ath>an>an>an> and an id="mmlsi9" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si9.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=d66e38d6b9961c5a6b57ffdb8705edf7" title="Click to view the MathML source">n≥1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si9.gif" overflow="scroll">n≥1ath>an>an>an> be integers, and let an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an> be a connected graph. If there exists a subgraph an id="mmlsi11" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si11.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=3850981dd03a7676ab5b4a9e8c53956b" title="Click to view the MathML source">Han>an class="mathContainer hidden">an class="mathCode">ath altimg="si11.gif" overflow="scroll">Hath>an>an>an> of an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an> such that for every vertex an id="mmlsi13" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=a3f1125ef2a0e770a434bcf184210e62" title="Click to view the MathML source">van>an class="mathContainer hidden">an class="mathCode">ath altimg="si13.gif" overflow="scroll">vath>an>an>an> of an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an>, the distance between an id="mmlsi13" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si13.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=a3f1125ef2a0e770a434bcf184210e62" title="Click to view the MathML source">van>an class="mathContainer hidden">an class="mathCode">ath altimg="si13.gif" overflow="scroll">vath>an>an>an> and an id="mmlsi11" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si11.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=3850981dd03a7676ab5b4a9e8c53956b" title="Click to view the MathML source">Han>an class="mathContainer hidden">an class="mathCode">ath altimg="si11.gif" overflow="scroll">Hath>an>an>an> is at most an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=966d7857928f37bb0b94d562436b5d66" title="Click to view the MathML source">man>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">math>an>an>an>, then we say that an id="mmlsi11" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si11.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=3850981dd03a7676ab5b4a9e8c53956b" title="Click to view the MathML source">Han>an class="mathContainer hidden">an class="mathCode">ath altimg="si11.gif" overflow="scroll">Hath>an>an>an> an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=966d7857928f37bb0b94d562436b5d66" title="Click to view the MathML source">man>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">math>an>an>an>-dominates an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an>. A tree whose maximum degree is at most an id="mmlsi5" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=abe12d4fc2b91a6d7f931eac42171b1d" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si5.gif" overflow="scroll">kath>an>an>an> is called a an id="mmlsi5" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=abe12d4fc2b91a6d7f931eac42171b1d" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si5.gif" overflow="scroll">kath>an>an>an>-tree. Define an id="mmlsi23" class="mathmlsrc"><a title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si23.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=e53021b46e627e442b26f9f5ee86b5c4">ass="imgLazyJSB inlineImage" height="18" width="429" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15003672-si23.gif">a>an class="mathContainer hidden">an class="mathCode">ath altimg="si23.gif" overflow="scroll">αl(G)=max{|S|:S⊆V(G),dG(x,y)≥lace class="nbsp">ace>for all distinctace class="nbsp">ace>x,y∈S}ath>an>an>an>, where an id="mmlsi24" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si24.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8e127b5e92ae21dc54bb6aa1e4312d92" title="Click to view the MathML source">d_G(x,y)an>an class="mathContainer hidden">an class="mathCode">ath altimg="si24.gif" overflow="scroll">dG(x,y)ath>an>an>an> denotes the distance between an id="mmlsi25" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si25.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=61592d9780942d7a733f48b8a0e660d1" title="Click to view the MathML source">xan>an class="mathContainer hidden">an class="mathCode">ath altimg="si25.gif" overflow="scroll">xath>an>an>an> and an id="mmlsi26" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si26.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=9737975c03524993126004c6fc7eeb35" title="Click to view the MathML source">yan>an class="mathContainer hidden">an class="mathCode">ath altimg="si26.gif" overflow="scroll">yath>an>an>an> in an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an>. We prove the following theorem and show that the condition is sharp. If an an id="mmlsi28" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si28.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=c608ff274d94067582fc110c4a4e811c" title="Click to view the MathML source">nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si28.gif" overflow="scroll">nath>an>an>an>-connected graph an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an> satisfies an id="mmlsi30" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si30.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=ed7fb96ae60f183d4ca8c93103efc0e6" title="Click to view the MathML source">α^2(m+1)(G)≤(k−1)n+1an>an class="mathContainer hidden">an class="mathCode">ath altimg="si30.gif" overflow="scroll">α2(m+1)(G)≤(k−1)n+1ath>an>an>an>, then an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an> has a an id="mmlsi5" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=abe12d4fc2b91a6d7f931eac42171b1d" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si5.gif" overflow="scroll">kath>an>an>an>-tree that an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=966d7857928f37bb0b94d562436b5d66" title="Click to view the MathML source">man>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">math>an>an>an>-dominates an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si1.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=8331d5fa9d995f1104d9d81cf34abbc3" title="Click to view the MathML source">Gan>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">Gath>an>an>an>. This theorem is a generalization of both a theorem of Neumann-Lara and Rivera-Campo on a spanning an id="mmlsi5" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si5.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=abe12d4fc2b91a6d7f931eac42171b1d" title="Click to view the MathML source">kan>an class="mathContainer hidden">an class="mathCode">ath altimg="si5.gif" overflow="scroll">kath>an>an>an>-tree in an an id="mmlsi28" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si28.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=c608ff274d94067582fc110c4a4e811c" title="Click to view the MathML source">nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si28.gif" overflow="scroll">nath>an>an>an>-connected graph and a theorem of Broersma on an an id="mmlsi4" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=966d7857928f37bb0b94d562436b5d66" title="Click to view the MathML source">man>an class="mathContainer hidden">an class="mathCode">ath altimg="si4.gif" overflow="scroll">math>an>an>an>-dominating path in an an id="mmlsi28" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si28.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=c608ff274d94067582fc110c4a4e811c" title="Click to view the MathML source">nan>an class="mathContainer hidden">an class="mathCode">ath altimg="si28.gif" overflow="scroll">nath>an>an>an>-connected graph.