کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646520 | 1632249 | 2016 | 9 صفحه PDF | دانلود رایگان |
For any two vertices xx and yy in a connected graph GG, an xx–yy path is a monophonic path if it contains no chord, and a longest xx–yy monophonic path is called an xx–yy detour monophonic path. For any vertex xx in GG, a set Sx⊆V(G)Sx⊆V(G) is an xx-detour monophonic set of GG if each vertex v∈V(G)v∈V(G) lies on an xx–yy detour monophonic path for some element yy in SxSx. The minimum cardinality of an xx-detour monophonic set of GG is the xx-detour monophonic number of GG, denoted by dmx(G)dmx(G). A subset TxTx of a minimum xx-detour monophonic set SxSx of GG is an xx-forcing subset for SxSx if SxSx is the unique minimum xx-detour monophonic set containing TxTx. An xx-forcing subset for SxSx of minimum cardinality is a minimum xx-forcing subset of SxSx. The forcing xx-detour monophonic number of SxSx, denoted by fdmx(Sx)fdmx(Sx), is the cardinality of a minimum xx-forcing subset for SxSx. The forcing xx-detour number of GG is fdmx(G)=min{fdmx(Sx)}fdmx(G)=min{fdmx(Sx)}, where the minimum is taken over all minimum xx-detour monophonic sets SxSx in GG. We determine bounds for it and find the same for some special classes of graphs. Also we show that for every pair s,ts,t of integers with 2≤s≤t2≤s≤t, there exists a connected graph GG such that fdmx(G)=sfdmx(G)=s and dmx(G)=tdmx(G)=t for some vertex xx in GG.
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 13, Issue 1, April 2016, Pages 76–84