2025-11-23T04:19:16.663058

Independent Bondage Number in Graphs under Girth Constraints

Gamlath, Pham, Wei

Given a finite, simple graph $G$, the independent bondage number of $G$ is the minimum size of an edge set such that its deletion results in a graph with strictly larger independent domination number than that of $G$. While the bondage number of graphs under girth constraints has been studied, very few results have yet been established for the independent bondage number. In this study, we establish upper bounds on the independent bondage number of planar graphs under given girth constraints, extending results on the bondage number by Fischermann, Rautenbach, and Volkmann and on the structures of planar graphs by Borodin and Ivanova. In particular, we identify additional structures and establish bounds on the independent bondage number for planar graphs with $Î´(G) \geq 2$ and $g(G)\geq 5$, $Î´(G)\geq 3$ and $g(G)\geq 4$, and $Î´(G) \geq 2$ and $g(G)\geq 10$.

academic

গ্রাফে স্বাধীন বন্ধন সংখ্যা গার্থ সীমাবদ্ধতার অধীনে

মৌলিক তথ্য

পেপার আইডি: 2411.01687
শিরোনাম: Independent Bondage Number in Graphs under Girth Constraints
লেখক: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
প্রকাশনার সময়: অক্টোবর ১৫, ২০২৫ (arXiv প্রাক-প্রিন্ট)
পেপার লিংক: https://arxiv.org/abs/2411.01687

সারসংক্ষেপ

একটি সীমিত সরল গ্রাফ $G$ দেওয়া হলে, গ্রাফ $G$ এর স্বাধীন বন্ধন সংখ্যা (independent bondage number) হল সর্বনিম্ন প্রান্ত সেটের আকার যা মুছে ফেলার পরে ফলস্বরূপ গ্রাফের স্বাধীন আধিপত্য সংখ্যা $G$ এর চেয়ে কঠোরভাবে বৃহত্তর হয়। যদিও গার্থ সীমাবদ্ধতার অধীনে গ্রাফের বন্ধন সংখ্যা অধ্যয়ন করা হয়েছে, স্বাধীন বন্ধন সংখ্যার ফলাফল এখনও অত্যন্ত সীমিত। এই গবেষণা প্রদত্ত গার্থ সীমাবদ্ধতার অধীনে সমতল গ্রাফের স্বাধীন বন্ধন সংখ্যার উপরের সীমা স্থাপন করে, Fischermann, Rautenbach এবং Volkmann এর বন্ধন সংখ্যা সম্পর্কিত ফলাফল এবং Borodin এবং Ivanova এর সমতল গ্রাফ কাঠামো সম্পর্কিত ফলাফল প্রসারিত করে। বিশেষত, অতিরিক্ত কাঠামো চিহ্নিত করা হয়েছে এবং $\delta(G) \geq 2$ এবং $g(G) \geq 5$ , $\delta(G) \geq 3$ এবং $g(G) \geq 4$ , এবং $\delta(G) \geq 2$ এবং $g(G) \geq 10$ পূরণকারী সমতল গ্রাফের স্বাধীন বন্ধন সংখ্যার সীমা স্থাপন করা হয়েছে।

গবেষণা পটভূমি এবং অনুপ্রেরণা

সমস্যা সংজ্ঞা এবং গুরুত্ব

১. মূল ধারণা:

স্বাধীন আধিপত্য সেট: শীর্ষবিন্দুর একটি সেট যা একই সাথে স্বাধীন এবং আধিপত্যশীল
স্বাধীন আধিপত্য সংখ্যা $\gamma_i(G)$ : সর্বনিম্ন স্বাধীন আধিপত্য সেটের মূলত্ব
স্বাধীন বন্ধন সংখ্যা $b_i(G)$ : সর্বনিম্ন প্রান্ত সেট $B$ এর আকার যেখানে $\gamma_i(G-B) > \gamma_i(G)$

२. গবেষণার তাৎপর্য:

প্রান্ত ব্যর্থতার ক্ষেত্রে নেটওয়ার্কের স্বাধীন আধিপত্য কাঠামোর দুর্বলতা পরিমাপ করে
আন্তঃসংযুক্ত নেটওয়ার্কের লিংক ব্যর্থতা বিশ্লেষণে গুরুত্বপূর্ণ প্রয়োগ মূল্য রয়েছে
ক্লাসিক্যাল আধিপত্য তত্ত্বের গবেষণা পরিধি প্রসারিত করে

३. বিদ্যমান গবেষণার সীমাবদ্ধতা:

ঐতিহ্যবাহী বন্ধন সংখ্যা $b(G)$ গার্থ সীমাবদ্ধতার অধীনে ইতিমধ্যে পদ্ধতিগতভাবে অধ্যয়ন করা হয়েছে
স্বাধীন বন্ধন সংখ্যা $b_i(G)$ সম্পর্কিত ফলাফল অত্যন্ত সীমিত, বিশেষত গার্থ সীমাবদ্ধতার শর্তে
নির্দিষ্ট গ্রাফ শ্রেণীর জন্য ধ্রুবক উপরের সীমা ফলাফলের অভাব

४. গবেষণা অনুপ্রেরণা:

Fischermann এবং অন্যদের (২০০३) সমতল গ্রাফের বন্ধন সংখ্যা গার্থ সীমাবদ্ধতা ফলাফল দ্বারা অনুপ্রাণিত
স্বাভাবিকভাবে অন্বেষণ করে যে স্বাধীন বন্ধন সংখ্যা গার্থ সীমাবদ্ধতার অধীনে অনুরূপ ধ্রুবক উপরের সীমা অর্জন করতে পারে কিনা
স্বাধীন বন্ধন সংখ্যা তত্ত্ব গবেষণার শূন্যতা পূরণ করে

মূল অবদান

१. চারটি প্রধান ধ্রুবক উপরের সীমা উপপাদ্য স্থাপন করা:

$\delta(G) \geq 3$ এবং $g(G) \geq 4$ হলে: $b_i(G) \leq 6$
$\delta(G) \geq 2$ এবং $g(G) \geq 5$ হলে: $b_i(G) \leq 5$
$\delta(G) \geq 2$ এবং $g(G) \geq 7$ হলে: $b_i(G) \leq 4$
$\delta(G) \geq 2$ এবং $g(G) \geq 10$ হলে: $b_i(G) \leq 3$

२. একাধিক মূল গ্রাফ কাঠামো কনফিগারেশন চিহ্নিত করা:

$\delta(G) \geq 2$ এবং $g(G) \geq 5$ এর জন্য: ১০টি অনিবার্য কনফিগারেশন চিহ্নিত করা
$\delta(G) \geq 3$ এবং $g(G) \geq 4$ এর জন্য: ३টি মূল কনফিগারেশন চিহ্নিত করা
প্রতিটি কনফিগারেশনের জন্য সংশ্লিষ্ট স্বাধীন বন্ধন সেট নির্মাণ করা

३. বিদ্যমান তত্ত্বগত কাঠামো প্রসারিত করা:

Fischermann এবং অন্যদের বন্ধন সংখ্যা ফলাফল স্বাধীন বন্ধন সংখ্যায় সাধারণীকরণ করা
Borodin এবং Ivanova এর সমতল গ্রাফ কাঠামো তত্ত্ব ব্যবহার এবং উন্নয়ন করা

४. পদ্ধতিগত প্রমাণ পদ্ধতি প্রদান করা:

অনিবার্য কাঠামো চিহ্নিত করতে স্রাব পদ্ধতি (discharging method) প্রয়োগ করা
প্রতিটি কাঠামোর জন্য গঠনমূলক স্বাধীন বন্ধন সেট প্রমাণ প্রদান করা

পদ্ধতি বিস্তারিত

তাত্ত্বিক ভিত্তি

সংজ্ঞা ব্যবস্থা:

গ্রাফ $G$ এর স্বাধীন বন্ধন সংখ্যা: $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
গার্থ $g(G)$ : গ্রাফে সবচেয়ে ছোট চক্রের দৈর্ঘ্য
ন্যূনতম ডিগ্রি $\delta(G)$ : গ্রাফে শীর্ষবিন্দুর ন্যূনতম ডিগ্রি

মূল লেম্মা:

উপপাদ্য १ (Priddy, Wang, Wei): অ-খালি গ্রাফ G এর জন্য,
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

মূল পদ্ধতি: স্রাব প্রযুক্তি

স্রাব পদ্ধতির নীতি: १. প্রাথমিক চার্জ বরাদ্দ: Euler সূত্রের তিনটি প্রাকৃতিক উপায় অনুযায়ী চার্জ বরাদ্দ করা

শীর্ষবিন্দু চার্জ: $d(v) - 6$ , মুখ চার্জ: $2\ell(f) - 6$ (শীর্ষবিন্দু স্রাব)
শীর্ষবিন্দু চার্জ: $2d(v) - 6$ , মুখ চার্জ: $\ell(f) - 6$ (মুখ স্রাব)
শীর্ষবিন্দু চার্জ: $d(v) - 4$ , মুখ চার্জ: $\ell(f) - 4$ (ভারসাম্যপূর্ণ স্রাব)

२. চার্জ পুনর্বিতরণ নিয়ম: ইতিবাচক চার্জ শীর্ষবিন্দু/মুখ থেকে নেতিবাচক চার্জ শীর্ষবিন্দু/মুখে প্রবাহিত করার জন্য নির্দিষ্ট নিয়ম ডিজাইন করা

३. কাঠামো চিহ্নিতকরণ: চূড়ান্ত চার্জ বিতরণ বিশ্লেষণের মাধ্যমে নির্দিষ্ট কাঠামোর অনিবার্যতা প্রমাণ করা

নির্দিষ্ট বাস্তবায়ন কৌশল

$\delta(G) \geq 2$ এবং $g(G) \geq 5$ এর ক্ষেত্রে:

স্রাব নিয়ম:

(R१) প্রতিটি २-ডিগ্রি শীর্ষবিন্দু প্রতিটি সংলগ্ন শীর্ষবিন্দু এবং প্রতিটি সংযুক্ত মুখ থেকে যথাক্রমে $\frac{1}{2}$ চার্জ গ্রহণ করে
(R२) প্রতিটি ३-ডিগ্রি শীর্ষবিন্দু প্রতিটি সংযুক্ত মুখ থেকে $\frac{1}{3}$ চার্জ গ্রহণ করে
(R३) নির্দিষ্ট ६-ডিগ্রি শীর্ষবিন্দুর চার্জ বরাদ্দ নিয়ম
(R४) নির্দিষ্ট ५-ডিগ্রি শীর্ষবিন্দুর চার্জ বরাদ্দ নিয়ম

মূল তথ্য যাচাইকরণ:

তথ্য १: প্রতিটি ডিগ্রি ≤४ শীর্ষবিন্দুর চূড়ান্ত চার্জ শূন্য
তথ্য २: ५+ ডিগ্রি শীর্ষবিন্দুর চার্জ বরাদ্দ পারস্পরিক একচেটিয়াতা
তথ্য ३-८: বিভিন্ন শীর্ষবিন্দু এবং মুখের অ-নেতিবাচক চার্জ নিশ্চিতকরণ

প্রধান ফলাফল

উপপাদ্য ७: $\delta(G) \geq 2$ এবং $g(G) \geq 5$ এর কাঠামো বৈশিষ্ট্য

প্রতিটি শর্ত পূরণকারী সমতল গ্রাফ $G$ অবশ্যই নিম্নলিখিত কনফিগারেশনগুলির একটি অন্তর্ভুক্ত করে:

(a) $(2,4^-)$ প্রান্ত বা $(3,3^-)$ প্রান্ত
(b) শীর্ষবিন্দু $v \in S(5^+, [d(v)-1]^+)$ এবং এর অবশিষ্ট প্রতিবেশী ४-ডিগ্রি শীর্ষবিন্দু বা $S(5^+,1^+)$ এর শীর্ষবিন্দু
(c)-(j) ८টি জটিল কনফিগারেশন যা ५-ডিগ্রি শীর্ষবিন্দু এবং २-ডিগ্রি প্রতিবেশীদের ५-মুখ ভাগ করে

উপপাদ্য ८: স্বাধীন বন্ধন সংখ্যা উপরের সীমা

$\delta(G) \geq 2$ এবং $g(G) \geq 5$ এর সমতল গ্রাফ $G$ এর জন্য: $b_i(G) \leq 5$

প্রমাণ পদ্ধতি: १. প্রতিটি কনফিগারেশনের জন্য আকার ≤५ এর প্রান্ত সেট $B$ নির্মাণ করা २. প্রমাণ করা যে $B$ মুছে ফেলার পরে স্বাধীন আধিপত্য সংখ্যা কঠোরভাবে বৃদ্ধি পায় ३. বৈপরীত্য এবং স্বাধীন আধিপত্য সেটের বৈশিষ্ট্য ব্যবহার করা

অন্যান্য প্রধান ফলাফল

উপপাদ্য १०: $\delta(G) \geq 3$ এবং $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

অনুসিদ্ধান্ত १: $\delta(G) \geq 2$ এবং $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (Cranston-West লেম্মার উপর ভিত্তি করে)

উপপাদ্য १३: $\delta(G) \geq 2$ এবং $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

পদ্ধতিগত উদ্ভাবন

१. স্বাধীন বন্ধন সংখ্যা গবেষণায় স্রাব পদ্ধতি প্রথমবার পদ্ধতিগতভাবে প্রয়োগ করা २. নতুন চার্জ বরাদ্দ কৌশল উন্নয়ন: স্বাধীন বন্ধন সংখ্যার বিশেষ বৈশিষ্ট্যের জন্য ডিজাইন করা ३. কাঠামো চিহ্নিতকরণ এবং বন্ধন সেট নির্মাণের সম্পূর্ণ কাঠামো স্থাপন করা

তাত্ত্বিক অবদান

१. ক্লাসিক্যাল ফলাফল প্রসারিত করা: বন্ধন সংখ্যা থেকে স্বাধীন বন্ধন সংখ্যায় সাধারণীকরণ २. তাত্ত্বিক শূন্যতা পূরণ করা: গার্থ সীমাবদ্ধতার অধীনে স্বাধীন বন্ধন সংখ্যার প্রথম পদ্ধতিগত ফলাফল প্রদান করা
३. নতুন গ্রাফ কাঠামো চিহ্নিত করা: স্বাধীন বন্ধন সংখ্যাকে প্রভাবিত করে এমন মূল কনফিগারেশন আবিষ্কার করা

প্রমাণ কৌশল

१. সূক্ষ্ম চার্জ বিশ্লেষণ: বিস্তারিত তথ্য যাচাইকরণের মাধ্যমে স্রাব প্রক্রিয়ার সঠিকতা নিশ্চিত করা २. গঠনমূলক প্রমাণ: প্রতিটি কনফিগারেশনের জন্য স্পষ্টভাবে স্বাধীন বন্ধন সেট নির্মাণ করা ३. কেস বিশ্লেষণের সম্পূর্ণতা: সমস্ত সম্ভাব্য কাঠামো কনফিগারেশন পরিপূর্ণতার সাথে পরীক্ষা করা

উপসংহার এবং আলোচনা

প্রধান উপসংহার

সমতল গ্রাফের স্বাধীন বন্ধন সংখ্যার গার্থ সীমাবদ্ধতার অধীনে সম্পূর্ণ উপরের সীমা ব্যবস্থা স্থাপন করা:

6, & \text{যদি } g(G) \geq 4 \text{ এবং } \delta(G) \geq 3 \\ 5, & \text{যদি } g(G) \geq 5 \text{ এবং } \delta(G) \geq 2 \\ 4, & \text{যদি } g(G) \geq 7 \text{ এবং } \delta(G) \geq 2 \\ 3, & \text{যদি } g(G) \geq 10 \text{ এবং } \delta(G) \geq 2 \end{cases}$$ ### সীমাবদ্ধতা १. **উপরের সীমার কঠোরতা অজানা**: এখনও উপরের সীমা অর্জনকারী চরম গ্রাফ উদাহরণ নির্মাণ করা হয়নি २. **শুধুমাত্র সমতল গ্রাফের জন্য**: অন্যান্য গ্রাফ শ্রেণীর ফলাফল অধ্যয়নের অপেক্ষায় রয়েছে ३. **গার্থ প্রয়োজনীয়তা অপেক্ষাকৃত উচ্চ**: নির্দিষ্ট ক্ষেত্রে গার্থ সীমাবদ্ধতা অত্যধিক কঠোর হতে পারে ### ভবিষ্যত দিকনির্দেশনা १. **কঠোরতা বিশ্লেষণ**: চরম উদাহরণ নির্মাণ বা উপরের সীমা উন্নত করা २. **গ্রাফ শ্রেণী প্রসারিত করা**: টোরাস গ্রাফ ইত্যাদি অন্যান্য গ্রাফ শ্রেণী অধ্যয়ন করা ३. **অ্যালগরিদম সমস্যা**: স্বাধীন বন্ধন সংখ্যা গণনার জন্য দক্ষ অ্যালগরিদম ডিজাইন করা ४. **প্রয়োগ গবেষণা**: নেটওয়ার্ক নির্ভরযোগ্যতা বিশ্লেষণে ব্যবহারিক প্রয়োগ অন্বেষণ করা ## গভীর মূল্যায়ন ### সুবিধা १. **তাত্ত্বিক অবদান উল্লেখযোগ্য**: প্রথমবার গার্থ সীমাবদ্ধতার অধীনে স্বাধীন বন্ধন সংখ্যা তত্ত্ব পদ্ধতিগতভাবে স্থাপন করা २. **পদ্ধতি কঠোর এবং সম্পূর্ণ**: স্রাব পদ্ধতি যথাযথভাবে প্রয়োগ করা, প্রমাণ বিস্তারিত এবং কঠোর ३. **ফলাফল সর্বজনীনতা রয়েছে**: একাধিক পরামিতি সমন্বয় অন্তর্ভুক্ত করে, সম্পূর্ণ ব্যবস্থা গঠন করে ४. **লেখা স্পষ্ট এবং নিয়মিত**: কাঠামো যুক্তিসঙ্গত, প্রযুক্তিগত বিবরণ সঠিকভাবে প্রকাশিত ### অপূর্ণতা १. **ব্যবহারিক প্রয়োগযোগ্যতা সীমিত**: প্রধানত বিশুদ্ধ তাত্ত্বিক ফলাফল, ব্যবহারিক প্রয়োগ পরিস্থিতি অস্পষ্ট २. **গণনা জটিলতা**: স্বাধীন বন্ধন সংখ্যার গণনা জটিলতা বিশ্লেষণ অন্তর্ভুক্ত নয় ३. **গ্রাফ শ্রেণী সীমাবদ্ধতা**: শুধুমাত্র সমতল গ্রাফ বিবেচনা করা, ফলাফলের প্রয়োগযোগ্যতা সীমিত করে ४. **চরম নির্মাণ অনুপস্থিত**: উপরের সীমা অর্জনকারী নির্দিষ্ট গ্রাফ উদাহরণ প্রদান করা হয়নি ### প্রভাব १. **একাডেমিক মূল্য উচ্চ**: গ্রাফ তত্ত্ব এবং সমন্বয় অপ্টিমাইজেশন, বিশেষত আধিপত্য তত্ত্বে গুরুত্বপূর্ণ পরিপূরক প্রদান করে २. **পদ্ধতিগত অবদান**: স্বাধীন বন্ধন সংখ্যায় স্রাব পদ্ধতির প্রয়োগ প্রদর্শনী মূল্য রয়েছে ३. **পরবর্তী গবেষণার ভিত্তি**: সম্পর্কিত সমস্যার আরও গবেষণার জন্য ভিত্তি স্থাপন করে ४. **পুনরুৎপাদনযোগ্যতা শক্তিশালী**: প্রমাণ প্রক্রিয়া বিস্তারিত, ফলাফল যাচাইকরণ এবং সম্প্রসারণ সহজ ### প্রযোজ্য পরিস্থিতি १. **তাত্ত্বিক গবেষণা**: গ্রাফ তত্ত্ব এবং সমন্বয় অপ্টিমাইজেশনের মৌলিক তাত্ত্বিক গবেষণা २. **নেটওয়ার্ক বিশ্লেষণ**: যোগাযোগ নেটওয়ার্ক এবং সামাজিক নেটওয়ার্কের দুর্বলতা বিশ্লেষণ ३. **অ্যালগরিদম ডিজাইন**: হিউরিস্টিক অ্যালগরিদম এবং আনুমানিক অ্যালগরিদমের তাত্ত্বিক ভিত্তি ४. **শিক্ষা প্রয়োগ**: গ্রাফ তত্ত্ব কোর্সে স্রাব পদ্ধতির সাধারণ প্রয়োগ উদাহরণ ## সংদর্ভ এই পেপারটি প্রধানত নিম্নলিখিত মূল সাহিত্য উল্লেখ করে: १. Fischermann, M., Rautenbach, D., & Volkmann, L. (२००३). সমতল গ্রাফ বন্ধন সংখ্যার উপর মন্তব্য २. Priddy, B., Wang, H., & Wei, B. (२०१९). গ্রাফের স্বাধীন বন্ধন সংখ্যা ३. Pham, A., & Wei, B. (२०२२). ন্যূনতম ডিগ্রি কমপক্ষে ३ এর সমতল গ্রাফের স্বাধীন বন্ধন সংখ্যা ४. Cranston, D. W., & West, D. B. (२०१७). গ্রাফ রঙ্গায়নের মাধ্যমে স্রাব পদ্ধতি পরিচয় ५. Borodin, O. V., & Ivanova, A. O. (२०१९). গার্থ কমপক্ষে ६ এর সমতল গ্রাফে २-ডিগ্রি শীর্ষবিন্দু কেন্দ্রিক ३-পথের সমস্ত কঠোর বর্ণনা