|
عنوان
|
برخی پارامترهای احاطه ای با به کارگیری عدد 2 در گراف ها
|
|
نوع پژوهش
|
پایان نامه
|
|
کلیدواژه‌ها
|
احاطه ای ایتالیایی، احاطه ای تام، احاطه ای رومی، احاطه ای رومی مضاعف، احاطه ای رومی شبه تام، احاطه ای رومی مضاعف شبه تام
|
|
چکیده
|
ﺩﺭ ﺍﯾﻦ ﺭﺳﺎﻟﻪ ﺧﻮﺍﺹ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯾﯽ ﻣﻮﺭﺩ ﺑﺮﺭﺳ ﻗﺮﺍﺭ ﻣﯿ ﯿﺮﻧﺪ ﮐﻪ ﺩﺭ ﺁﻧﻬﺎ ﻋﺪﺩ 2 ﺑ ﺎﺭ ﺭﻓﺘﻪ ﺍﺳﺖ ﮐﻪ ﺑﺮﺧ ﺍﺯ ﺁﻧﻬﺎ ﻋﺒﺎﺭﺗﻨﺪ ﺍﺯ γqtdR(G)، (G) γqtI ﻭ (G)2.γqtr ﻫﻤﭽﻨﯿﻦ ﮐﺮﺍﻥﻫﺎﯼ ﺑﺎﻻ ﻭ ﭘﺎﯾﯿﻦ ﺑﺮﺍﯼ ﺍﯾﻦ ﭘﺎﺭﺍﻣﺘﺮﻫﺎ ﺍﺭﺍﺋﻪ ﻣ ﮐﻨﯿﻢ. ﺳﭙﺲ ﺑﺮﺧ ﮐﺮﺍﻥﻫﺎﯼ ﻗﺎﺑﻞ ﻭﺻﻮﻝ ﺭﺍ ﻣﻌﺮﻓ ﮐﺮﺩﻩ ﻭ ﺩﺭ ﺍﺩﺍﻣﻪ ﺍﺭﺗﺒﺎﻁ ﺍﯾﻦ ﭘﺎﺭﺍﻣﺘﺮﻫﺎ ﺑﺎ ﺳﺎﯾﺮ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﺍﺣﺎﻃﻪﺍﯼ ﺭﺍ ﻣﻮﺭﺩ ﺑﺮﺭﺳ ﻗﺮﺍﺭ ﻣ ﺩﻫﯿﻢ. ﻫﻤﭽﻨﯿﻦ ﺭﻭﺍﺑﻂ ﻧﻮﺭﺩﻫﺎﻭﺱ⁃ﮔﺎﺩﻡ ﺭﺍ ﺑﺮﺍﯼ ﭘﺎﺭﺍﻣﺘﺮﻫﺎﯼ ﺫﮐﺮ ﺷﺪﻩ ﺭﺍ ﻣﻮﺭﺩ ﻣﻄﺎﻟﻌﻪ ﻗﺮﺍﺭ ﻣ ﺩﻫﯿﻢ. ﺩﺭ ﺍﺩﺍﻣﻪ ﺑﺎ ﺍﺭﺍﺋﻪ ﺗﻌﺮﯾﻒ ﻣﻔﺎﻫﯿﻢ ﺟﺪﯾﺪ ﺑﺎﻧﺪﺍﮊ، ﺯﯾﺮ ﺗﻘﺴﯿﻢ ﻭ ﺗﻘﻮﯾﺖ ﮐﻨﻨﺪﻩ ﺍﻋﺪﺍﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭﻣﻦ ﻣﻀﺎﻋﻒ ﺷﺒﻪ ﺗﺎﻡ، ﺍﯾﺘﺎﻟﯿﺎﯾﯽ ﺷﺒﻪ ﺗﺎﻡ ﻭ 2⁃ﺭﻧﮕﯿﻦ ﮐﻤﺎﻥ ﺷﺒﻪ ﺗﺎﻡ ﺭﺍ ﺑﺮﺭﺳ ﺧﻮﺍﻫﯿﻢ ﮐﺮﺩ. ﺩﺭ ﺍﯾﻦ ﻗﺴﻤﺖ ﺑﺮﺧ ﻣﻮﺍﺭﺩ ﻣﺬﮐﻮﺭ ﮐﻪ ﺩﺭ ﺍﺣﺎﻃﻪﮔﺮﻫﺎﯼ ﺭﻭﻣﻦ ﺷﺒﻪ ﺗﺎﻡ، ﺭﻭﻣﻦ ﻣﻀﺎﻋﻒ
ﺗﺎﻡ ، ﺍﯾﺘﺎﻟﯿﺎﯾﯽ ﺗﺎﻡ ﻭ 2⁃ﺭﻧﮕﯿﻦ ﮐﻤﺎﻥ ﺷﺒﻪ ﺗﺎﻡ ﺍﺛﺒﺎﺕ ﺷﺪﻩﺍﻧﺪ، ﺑﯿﺎﻥ ﻣ ﮐﻨﯿﻢ.
(i) ﻓﺮﺽ ﮐﻨﯿﺪ G ﯾ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ n ﺑﺎ ﺑﯿﺸﺘﺮﯾﻦ ﺩﺭﺟﻪ 2 ≥ ∆(G) ﺑﺎﺷﺪ، ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: 2 + ∆(G) − n ≤ (G)
(ii) ﻫﺮﮔﺎﻩ G ﯾ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ n ﺑﺎﺷﺪ ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: )2 − ρ(G)(δ(G) − n ≤ γqtR(G) .
(iii) ﻫﺮﮔﺎﻩ G ﯾ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ 4 ≥ n، ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: 5 + n ≤ γqtR(G) + γqtR(G) ≤ 7.
(iv) ﺑﺮﺍﯼ ﻫﺮ ﮔﺮﺍﻑ ﻏﯿﺮ ﺑﺪﯾﻬ G، γ(G)3 ≤ γqtR(G) ≤ ρ(G) − γ(G)2.
(v) ﻫﺮﮔﺎﻩ G ﯾ ﮔﺮﺍﻑ ﻫﻤﺒﻨﺪ ﺍﺯ ﻣﺮﺗﺒﻪ n ﺑﺎﺷﺪ، ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: 1 + γ(G) ≥ γqtR(G) . ﺑﻪ ﻋﻼﻭﻩ 1 + γ(G) = γqtR(G) ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ
2P ∼= G ﻭ ﻫﻤﭽﻨﯿﻦ 2 + γ(G) = γqtR(G) ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ ﯾ ﺍﺯ ﺷﺮﺍﯾﻂ ﺯﯾﺮ ﺑﺮﻗﺮﺍﺭ ﺑﺎﺷﺪ.
(a) 2P ≇ G ﺭﺃﺳ ﺍﺯ ﺩﺭﺟﻪ γ(G) − n ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ.
(b) G ﺩﺍﺭﺍﯼ ﺩﻭ ﺭﺃﺱ ﻣﺠﺎﻭﺭ u ﻭ v ﺑﺎﺷﺪ ﺑﻪ ﻃﻮﺭﯼﮐﻪ γ(G) − n = v})| .|∂({u,
(vi) ﻫﺮﮔﺎﻩ G ﯾ ﮔﺮﺍﻑ ﻫﻤﺒﻨﺪ ﺍﺯ ﻣﺮﺗﺒﻪ 2 ≥ n(G) ﺑﺎﺷﺪ ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: 1 − γtR(G)2 ≤ γtdR(G) ≤ 1 + γtR(G) . ﺑﻌﻼﻭﻩ ﮐﺮﺍﻥ ﭘﺎﯾﯿﻦ
ﺯﻣﺎﻧ ﻗﺎﺑﻞ ﻭﺻﻮﻝ ﺍﺳﺖ ﮐﻪ 1 − n = ∆ ﻭ ﮐﺮﺍﻥ ﺑﺎﻻ ﻗﺎﺑﻞ ﻭﺻﻮﻝ ﺍﺳﺖ . (vii) ﻓﺮﺽ ﮐﻨﯿﻢ G ﮔﺮﺍﻓ ﺑﺪﻭﻥ ﺭﺃﺱ ﺗﻨﻬﺎ ﺍﺯ ﻣﺮﺗﺒﻪ n ، 2 ≥ δ(G) ﺑﺎﺷﺪ، ﺩﺭ ﺍﯾﻦ ﺻﻮﺭﺕ: n + γt(G) ≤ (G)
ﺩﺭ ﺍﯾﻦ ﻃﺮﺡ ﻫﻤﺎﻥﻃﻮﺭ ﮐﻪ ﮔﻔﺘﻪ ﺷﺪ ﺳﻌ ﺑﺮ ﺍﯾﻦ ﺍﺳﺖ ﮐﻪ ﻧﺘﺎﯾﺞ ﻣﺬﮐﻮﺭ ﺭﺍ ﺑﺮﺍﯼ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭﻣﻦ ﻣﻀﺎﻋﻒ ﺷﺒﻪ ﺗﺎﻡ، ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺍﯾﺘﺎﻟﯿﺎﯾﯽ ﺷﺒﻪ ﺗﺎﻡ ﻭ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ 2⁃ﺭﻧﮕﯿﻦ ﮐﻤﺎﻥ ﺷﺒﻪ ﺗﺎﻡ ﺗﻌﻤﯿﻢ ﺩﺍﺩﻩ ﻭ ﮐﺮﺍﻥﻫﺎﯼ ﺑﺎﻻ ﻭ ﭘﺎﯾﯿﻦ ﺭﺍ ﺑﺮﺍﯼ ﺍﯾﻦ ﭘﺎﺭﺍﻣﺘﺮﻫﺎ ﺗﻌﺮﯾﻒ ﮐﻨﯿﻢ. ﻫﻤﭽﻨﯿﻦ ﻋﺪﺩ ﺑﺎﻧﺪﺍﮊ ، ﺗﻘﻮﯾﺖ ﮐﻨﻨﺪﻩ ﻭ ﺑﺮﺧ ﺧﻮﺍﺹ ﻋﻤﻮﻣ ﺍﺯ ﻗﺒﯿﻞ ﺭﺍﺑﻄﻪ ﺍﻋﺪﺍﺩ ﻣﺬﮐﻮﺭ ﺑﺎ ﺑﯿﺸﺘﺮﯾﻦ ﻭ ﮐﻤﺘﺮﯾﻦ ﺩﺭﺟﻪ ﮔﺮﺍﻑ ﻭ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ، ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ ﺭﻭﻣﻦ ﻭ ﻋﺪﺩ ﺍﺣﺎﻃﻪﺍﯼ
ﺗﺎﻡ ﺭﺍ ﺑﻪ ﺩ
|
|
پژوهشگران
|
شیرین بابایی (دانشجو)، سید محمود شیخ الاسلامی کاوکانی (استاد راهنما)، جعفر امجدی زین الحاجلو (استاد راهنما)، ُسعید کوثری (استاد مشاور)
|