-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 b=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≥2$k\ge 2$, b=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≥2$l\ge 2$, b=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≥0$m\ge 0$ and b=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≥1$n\ge 1$ be integers, and let b=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">G$G$ be a connected graph. If there exists a subgraph b=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">H$H$ of b=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">G$G$ such that for every vertex b=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">v$v$ of b=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">G$G$, the distance between b=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">v$v$ and b=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">H$H$ is at most b=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">m$m$, then we say that b=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">H$H$ b=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">m$m$-dominates b=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">G$G$. A tree whose maximum degree is at most i5" class="mathmlsrc">b=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">k is called a i5" class="mathmlsrc">b=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">k-tree. Define b=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003672&_mathId=si23.gif&_user=111111111&_pii=S0012365X15003672&_rdoc=1&_issn=0012365X&md5=e53021b46e627e442b26f9f5ee86b5c4">, where b=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">db>Gb>(x,y) denotes the distance between b=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">x$x$ and b=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">y$y$ in b=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">G$G$. We prove the following theorem and show that the condition is sharp. If an b=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">n$n$-connected graph b=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">G$G$ satisfies b=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+1${\alpha }^{2(m+1)}\left(G\right)\le (k-1)n+1$, then b=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">G$G$ has a i5" class="mathmlsrc">b=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">k-tree that b=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">m$m$-dominates b=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">G$G$. This theorem is a generalization of both a theorem of Neumann-Lara and Rivera-Campo on a spanning i5" class="mathmlsrc">b=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">k-tree in an b=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">n$n$-connected graph and a theorem of Broersma on an b=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">m$m$-dominating path in an b=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">n$n$-connected graph.