The forcing vertex detour monophonic number of a graph

详细信息    查看全文

• 作者：P. Titus ; ^{titusvino@yahoo.com" class="auth_mail" title="E-mail the corresponding author} ; P. Balakrishnan ^{gangaibala1@yahoo.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Detour monophonic path ; Vertex detour monophonic number ; Forcing vertex detour monophonic number
• 刊名：?AKCE International Journal of Graphs and Combinatorics
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：13
• 期：1
• 页码：76-84
• 全文大小：318 K

文摘

For any two vertices rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x and rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y in a connected graph rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G, an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x–rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y path is a monophonic path if it contains no chord, and a longest rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x–rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y monophonic path is called an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x–rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y detour monophonic path. For any vertex rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x in rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G, a set rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si82.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1a3e183502a04ec48a0806b8a50638ca" title="Click to view the MathML source">S_x⊆V(G)r hidden">roll">row>Srow>row>xrow>⊆Vrow>(G)row> is an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic set of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G if each vertex rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si85.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=344543c430fb3c1ebaf9458f6eea154e" title="Click to view the MathML source">v∈V(G)r hidden">roll">v∈Vrow>(G)row> lies on an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x–rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y detour monophonic path for some element rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si39.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6d1fc89664b3bfabeb6248dd880639cf" title="Click to view the MathML source">yr hidden">roll">y in rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow>. The minimum cardinality of an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic set of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G is the rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic number of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G, denoted by rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si21.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=feb18e7372cb8069cf2c5bf3b8db2bca" title="Click to view the MathML source">dm_x(G)r hidden">roll">drow>mrow>row>xrow>row>(G)row>. A subset rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si95.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=3415238153e5f94c473dd5b4ab01b564" title="Click to view the MathML source">T_xr hidden">roll">row>Trow>row>xrow> of a minimum rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic set rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow> of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G is an rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-forcing subset for rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow> if rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow> is the unique minimum rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic set containing rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si95.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=3415238153e5f94c473dd5b4ab01b564" title="Click to view the MathML source">T_xr hidden">roll">row>Trow>row>xrow>. An rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-forcing subset for rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow> of minimum cardinality is a minimum rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-forcing subset of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow>. The forcing rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic number of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow>, denoted by rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si110.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=6bd0485b39e1073e44a03f6ac3ba00e7" title="Click to view the MathML source">f_dmx(S_x)r hidden">roll">row>frow>row>drow>mrow>row>xrow>row>row>(row>Srow>row>xrow>)row>, is the cardinality of a minimum rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-forcing subset for rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow>. The forcing rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour number of rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G is rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si115.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=48c025130391b86bcaaf0f8991be4d4b" title="Click to view the MathML source">f_dmx(G)=min{f_dmx(S_x)}r hidden">roll">row>frow>row>drow>mrow>row>xrow>row>row>(G)row>=minrow>{row>frow>row>drow>mrow>row>xrow>row>row>(row>Srow>row>xrow>)row>}row>, where the minimum is taken over all minimum rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x-detour monophonic sets rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si89.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=1511492fd828be9eaaea5513cbccf4bc" title="Click to view the MathML source">S_xr hidden">roll">row>Srow>row>xrow> in rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G. We determine bounds for it and find the same for some special classes of graphs. Also we show that for every pair rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si119.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=0a79d1c04150b62229656612abe6af23" title="Click to view the MathML source">s,tr hidden">roll">s,t of integers with rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si120.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=5d7a2015fc861367b51bcfa61b9e1262" title="Click to view the MathML source">2≤s≤tr hidden">roll">2≤s≤t, there exists a connected graph rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G such that rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si9.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=db14658db80baeeb71166333f67cde6a" title="Click to view the MathML source">f_dmx(G)=sr hidden">roll">row>frow>row>drow>mrow>row>xrow>row>row>(G)row>=s and rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si7.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=68dc62b81e9c560aaa4b16d9f0647068" title="Click to view the MathML source">dm_x(G)=tr hidden">roll">drow>mrow>row>xrow>row>(G)row>=t for some vertex rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si23.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=47111d06f7d656c5af6ed47d4c861f06" title="Click to view the MathML source">xr hidden">roll">x in rc">rmulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0972860016300287&_mathId=si1.gif&_user=111111111&_pii=S0972860016300287&_rdoc=1&_issn=09728600&md5=b675c1a07169aa7bc1b337c50e7cffe7" title="Click to view the MathML source">Gr hidden">roll">G.