Mathematical Researches

fa عدد زیرتقسیم m - امن دایم در گرافها Eternal m- Security Subdivision Numbers in Graphs نظریه نمودار جبری Algebraic Graph Theory علمی پژوهشی بنیادی S فرض کنید <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image002.png" width="60" > گرافی با مجموعه رئوس<img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image004.png" width="9" > و مجموعه یالهای <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image006.png" width="9" > باشد. مجموعه <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image008.png" width="33" > را یک مجموعه احاطه گر در <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > نامند هرگاه هر رأس از <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image012.png" width="32" > با حداقل یک رأس از <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image014.png" width="7" > مجاور باشد. مجموعه احاطه گر <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image016.png" width="12" > از گراف <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > را یک مجموعه 1- امن دایم گویند هرگاه به ازای هر عدد صحیح مثبت <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image018.png" width="8" > و هر دنباله<img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image020.png" width="49" >  از رئوس، دنباله ای مانند <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image022.png" width="50" >  با شرط <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image024.png" width="50" > موجود باشد که <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image026.png" width="40" >  یا <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="48" > و  <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image030.png" width="136" > یک مجموعه احاطه گر باشد. اگر روی هریک از رئوس یک مجموعه 1- امن دایم در <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > یک محافظ قرار دهیم، آنگاه به ازای هر دنباله از حملات به رئوس، با حرکت یک محافظ در امتداد یکی از یالهای مجاور آن، مجموعه حاصل، باز هم امن باقی می ماند. اگر به ازای هر دنباله از حملات به رئوس <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" >، تمام محافظان بتوانند در امتداد یکی از یالهای مجاور حرکت کنند و مجموعه حاصل باز هم امن بماند، آنگاه این مجموعه را یک مجموعه <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم نامند. کمترین تعداد اعضای یک مجموعه <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم را عدد <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > نامیده و با <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image034.png" width="36" > نشان می دهند.<br>  زیرتقسیم یال <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image036.png" width="40" > از <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > عبارت است از حذف <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image038.png" width="7" > و افزودن رأس جدید <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image040.png" width="10" > و یالهای <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image042.png" width="18" > و <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image044.png" width="17" >. عدد زیرتقسیم <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" >، <img alt="" height="19" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image046.png" width="48" >، عبارت است از کمترین تعداد یالهایی از <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="9" > که با زیرتقسیم آنها عدد <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم گراف افزایش می یابد. در این مقاله نشان می دهیم که عدد زیرتقسیم <img alt="" height="17" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="21" > امن دایم <a>در</a><a href="#_msocom_1" id="_anchor_1" name="_msoanchor_1"><span dir="RTL">[a1]</span></a>  هر گراف حداکثر 3 است.  <div> <hr align="left" size="1" width="33%" > <div> <div id="_com_1"><a name="_msocom_1"></a><span dir="LTR"> <a href="#_msoanchor_1">[a1]</a></span></div> </div> </div> Let <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image002.png" width="76" > be a simple graph with vertex set <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image004.png" width="11" > and edges set <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image006.png" width="11" >. A set <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image008.png" width="40" > is a dominating<br> set if every vertex in <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image010.png" width="42" > is adjacent to at least one vertex  in <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image012.png" width="9" >. An eternal 1-secure set of a graph G is defined as a dominating set <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image014.png" width="15" > such that for any positive integer k and any sequence <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image016.png" width="80" > of vertices, there exists a sequence of guards  <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image018.png" width="82" > with <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image020.png" width="61" > and either <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image022.png" width="49" > or <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image024.png" width="57" > and <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image026.png" width="164" > is a dominating set. If we take a guard on every vertex in an eternal 1-secure set, then for any sequence of attacks to vertices of the graph only by moving one guard during one of the edges adjacent with the vertex, the result set still remains secure. Now let for every sequence of attacks to vertices, all guards could move during one of the edges adjacent with the vertex and the result set still remains secure. This set is called eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >-  secure set. The eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >-  security number <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image030.png" width="44" > is defined as the minimum number of an eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >- <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="4" >secure set. secure set in G. An edge <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image034.png" width="79" > is subdivided if the edge <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image036.png" width="18" > is deleted and a new vertex <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image038.png" width="9" > is added, along with two new edges<img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image040.png" width="22" > and <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image042.png" width="18" >. The eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >- security subdivision number <img alt="" height="22" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image044.png" width="59" > of a graph <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image046.png" width="11" > is the minimum cardinality of a set of edges that must be subdivided (where each edge in <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image046.png" width="11" > can be subdivided at most once) in order to increase the eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >- <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image032.png" width="4" >security number of <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image046.png" width="11" > to increase the eternal m- security number of G. In this paper, we show that the eternal <img alt="" height="20" src="file:///C:UsersadminAppDataLocalTempmsohtmlclip11clip_image028.png" width="14" >- security subdivision number is at most 3 for any nontrivial graph .<br>   عدد احاطه ای - مجموعه -m امن دایم- زیرتقسیم یک یال- عدد زیرتقسیم احاطه ای- عدد زیرتقسیم -m امن دایم. eternal m- secure set, eternal m- security number, eternal m- security subdividion number 235 242 http://mmr.khu.ac.ir/browse.php?a_code=A-10-594-1&slc_lang=fa&sid=1 Maryam Atapour مریم عطاپور m.atapour@bonabu.ac.ir 10031947532846005430 10031947532846005430 Yes دانشگاه بناب