2025-11-22T11:22:16.125593

Stability in Bondy's theorem on paths and cycles

Ning, Yuan

In this paper, we study the stability result of a well-known theorem of Bondy. We prove that for any 2-connected non-hamiltonian graph, if every vertex except for at most one vertex has degree at least $k$, then it contains a cycle of length at least $2k+2$ except for some special families of graphs. Our results imply several previous classical theorems including a deep and old result by Voss. We point out our result on stability in Bondy's theorem can directly imply a positive solution (in a slight stronger form) to the following problem: Is there a polynomial time algorithm to decide whether a 2-connected graph $G$ on $n$ vertices has a cycle of length at least $\min\{2Î´(G)+2,n\}$. This problem originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin, Golovach, Sagunov and Simonov, although a stronger problem was solved by them by completely different methods. Our theorem can also help us to determine all extremal graphs for wheels on odd number of vertices. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized TurÃ¡n problem.

academic

বন্ডি উপপাদ্যে পথ এবং চক্রের স্থিতিশীলতা

মৌলিক তথ্য

পত্র আইডি: 2207.13650
শিরোনাম: বন্ডি উপপাদ্যে পথ এবং চক্রের স্থিতিশীলতা
লেখক: বো নিং (নানকাই বিশ্ববিদ্যালয়), লং-টু ইউয়ান (পূর্ব চীন সাধারণ বিশ্ববিদ্যালয়)
শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
প্রকাশনার সময়: ২০২২ সালের জুলাইয়ে জমা দেওয়া, ২০২৩ সালের ডিসেম্বরে সংশোধিত
পত্র লিঙ্ক: https://arxiv.org/abs/2207.13650

সারসংক্ষেপ

এই পত্রটি বিখ্যাত বন্ডি উপপাদ্যের স্থিতিশীলতা ফলাফল অধ্যয়ন করে। লেখকরা প্রমাণ করেছেন যে যেকোনো ২-সংযুক্ত অ-হ্যামিলটোনীয় গ্রাফের জন্য, যদি সর্বাধিক একটি শীর্ষবিন্দু ছাড়া অন্য সকল শীর্ষবিন্দুর ডিগ্রি কমপক্ষে k হয়, তাহলে গ্রাফটি কমপক্ষে ২k+২ দৈর্ঘ্যের একটি চক্র ধারণ করে, কিছু বিশেষ গ্রাফ পরিবার ছাড়া। এই ফলাফল একাধিক ক্লাসিক্যাল উপপাদ্য অন্তর্ভুক্ত করে, যার মধ্যে রয়েছে ভস্-এর গভীর ফলাফল। লেখকরা নির্দেশ করেন যে বন্ডি উপপাদ্যের স্থিতিশীলতা সম্পর্কিত তাদের ফলাফল একটি সমস্যার ইতিবাচক সমাধান সরাসরি প্রদান করে: n শীর্ষবিন্দুর ২-সংযুক্ত গ্রাফ G-তে কমপক্ষে min{2δ(G)+2,n} দৈর্ঘ্যের চক্র রয়েছে কিনা তা নির্ধারণ করার জন্য বহুপদী সময়ের অ্যালগরিদম বিদ্যমান কিনা।

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

মূল সমস্যা: এই পত্রটি গ্রাফের চক্র দৈর্ঘ্য এবং ন্যূনতম ডিগ্রির মধ্যে সম্পর্ক অধ্যয়ন করে, বিশেষত "প্রায় নিয়মিত" গ্রাফে (একটি শীর্ষবিন্দু ছাড়া সকল শীর্ষবিন্দুর ডিগ্রি একই) দীর্ঘ চক্রের অস্তিত্ব সমস্যায়।
গুরুত্ব:
- এই সমস্যাটি চরম গ্রাফ তত্ত্বের মূল বিষয়বস্তু, হ্যামিলটোনীয় চক্র তত্ত্বের সাথে ঘনিষ্ঠভাবে সম্পর্কিত
- বর্ণালী গ্রাফ তত্ত্ব এবং সাধারণীকৃত টুরান সমস্যায় গুরুত্বপূর্ণ প্রয়োগ রয়েছে
- অ্যালগরিদমিক গ্রাফ তত্ত্বের জন্য তাত্ত্বিক ভিত্তি প্রদান করে
বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
- ডিরাক উপপাদ্য সকল শীর্ষবিন্দুর ডিগ্রি যথেষ্ট বড় হওয়ার দাবি করে
- বন্ডি উপপাদ্য শর্ত শিথিল করলেও, স্থিতিশীলতা বিশ্লেষণের অভাব রয়েছে
- চরম গ্রাফ কাঠামোর সম্পূর্ণ বর্ণনার অভাব রয়েছে
গবেষণার প্রেরণা:
- চরম গ্রাফ তত্ত্বে স্থিতিশীলতা ফলাফল দ্বারা অনুপ্রাণিত
- ফোমিন এবং অন্যদের দ্বারা উত্থাপিত অ্যালগরিদমিক সমস্যা সমাধান করা
- বিজোড় চাকা গ্রাফের চরম গ্রাফ কাঠামো নির্ধারণ করা

মূল অবদান

প্রধান উপপাদ্য: বন্ডি উপপাদ্যের স্থিতিশীলতা সংস্করণ প্রমাণ করা (উপপাদ্য ১.৬), প্রদত্ত ডিগ্রি শর্তে চক্র দৈর্ঘ্য সীমাবদ্ধ চরম গ্রাফ সম্পূর্ণভাবে বর্ণনা করা
অ্যালগরিদমিক প্রয়োগ: ২-সংযুক্ত গ্রাফে কমপক্ষে min{2δ(G)+2,n} দৈর্ঘ্যের চক্র রয়েছে কিনা তা নির্ধারণের জন্য বহুপদী সময়ের অ্যালগরিদম প্রদান করা
তাত্ত্বিক একীকরণ: একাধিক ক্লাসিক্যাল ফলাফল (আলি-স্টেটন উপপাদ্য, নিকিফোরভ-ইউয়ান উপপাদ্য ইত্যাদি) একটি কাঠামোর অধীনে একীভূত করা
চরম গ্রাফ বর্ণনা: বিজোড় চাকা গ্রাফ W₂ₖ₊₃ এর চরম গ্রাফ কাঠামো সম্পূর্ণভাবে নির্ধারণ করা
পদ্ধতিগত উদ্ভাবন: "পথ দ্রাক্ষালতা" কৌশল ব্যবহার করা, ঐতিহ্যবাহী চরম গ্রাফ তত্ত্ব পদ্ধতি থেকে ভিন্ন

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

কাজের সংজ্ঞা

ইনপুট: ২-সংযুক্ত অ-হ্যামিলটোনীয় n-শীর্ষবিন্দু গ্রাফ G, যেখানে সর্বাধিক একটি শীর্ষবিন্দু ছাড়া অন্য সকল শীর্ষবিন্দুর ডিগ্রি কমপক্ষে k≥2 আউটপুট: G-তে কমপক্ষে ২k+२ দৈর্ঘ্যের চক্র রয়েছে কিনা তা নির্ধারণ করা, যদি না থাকে তাহলে G-এর কাঠামো বর্ণনা করা সীমাবদ্ধতা: গ্রাফের পরিধি c(G)≤२k+१

মূল প্রযুক্তিগত পদ্ধতি

১. পথ দ্রাক্ষালতা কৌশল

সর্বাধিক পথ P = x₁x₂...xₘ নির্বাচন করা, যাতে ডিগ্রি k-এর চেয়ে কম শীর্ষবিন্দুর সংখ্যা সর্বনিম্ন হয়
গ্রাফের २-সংযোগযোগ্যতা ব্যবহার করে পথের মধ্যে সংযোগ তৈরি করা
প্রতিবেশী বিশ্লেষণের মাধ্যমে গ্রাফের কাঠামো নির্ধারণ করা

२. কেস বিশ্লেষণ কাঠামো

পত্রটি প্রমাণকে দুটি প্রধান ক্ষেত্রে বিভক্ত করে:

কেস १: নির্দিষ্ট শর্ত পূরণকারী শীর্ষবিন্দু জোড়া (i,j) বিদ্যমান

উপকেস १.१: প্রতিটি সর্বাধিক পথে সর্বাধিক এক জোড়া এই ধরনের শীর্ষবিন্দু জোড়া রয়েছে
উপকেস १.२: কমপক্ষে দুটি এই ধরনের শীর্ষবিন্দু জোড়া বিদ্যমান

কেস २: কেস १ ঘটে না, কিন্তু x₁ এবং xₘ উভয়ের প্রতিবেশীতে একযোগে অন্তর্ভুক্ত একটি শীর্ষবিন্দু বিদ্যমান

३. মূল লেম্মা

লেম্মা २.३: २-সংযুক্ত গ্রাফ G এবং শীর্ষবিন্দু u,v-এর জন্য, যদি দীর্ঘতম (u,v)-পথ সর্বাধিক k+१ টি শীর্ষবিন্দু ধারণ করে, এবং u,v এবং সর্বাধিক একটি অন্যান্য শীর্ষবিন্দু ছাড়া অন্য সকল শীর্ষবিন্দুর ডিগ্রি কমপক্ষে k হয়, তাহলে G-{u,v} = ℓKₖ₋₁∪K₁ অথবা G-{u,v} = ℓKₖ₋₁।

প্রযুক্তিগত উদ্ভাবনী বিন্দু

१. ডিগ্রি শর্তের নির্ভুল পরিচালনা: "সর্বাধিক একটি ব্যতিক্রম শীর্ষবিন্দু" শর্তের চতুর পরিচালনা, যা ঐতিহ্যবাহী ন্যূনতম ডিগ্রি শর্তের চেয়ে আরও সূক্ষ্ম

२. কাঠামো বিয়োজন পদ্ধতি: পথ নির্বাচন এবং প্রতিবেশী বিশ্লেষণের মাধ্যমে জটিল গ্রাফ কাঠামোকে পরিচালনাযোগ্য উপাদানে বিয়োজিত করা

३. চরম গ্রাফের সম্পূর্ণ শ্রেণীবিভাগ: শুধুমাত্র চক্র দৈর্ঘ্যের নিম্ন সীমা প্রমাণ করা নয়, বরং নিম্ন সীমা অর্জনকারী চরম গ্রাফ সম্পূর্ণভাবে বর্ণনা করা

পরীক্ষামূলক সেটআপ

এই পত্রটি বিশুদ্ধ তাত্ত্বিক গণিত পত্র, যা পরীক্ষামূলক যাচাইকরণ জড়িত নয়। সমস্ত ফলাফল কঠোর গাণিতিক প্রমাণের মাধ্যমে প্রাপ্ত।

তাত্ত্বিক যাচাইকরণ পদ্ধতি

গঠনমূলক প্রমাণ: প্রতিটি চরম গ্রাফ শ্রেণীর জন্য যাচাই করা যে এটি সত্যিই শর্ত পূরণ করে
প্রমাণ দ্বন্দ্ব দ্বারা: অন্য কোনো কাঠামো বিদ্যমান বলে অনুমান করা এবং বিরোধিতা উদ্ভব করা
আবর্তক বিশ্লেষণ: বিভিন্ন প্যারামিটার মানের জন্য আলাদাভাবে পরিচালনা করা

প্রধান ফলাফল

উপপাদ্য १.६ (প্রধান ফলাফল)

G যদি २-সংযুক্ত অ-হ্যামিলটোনীয় n-শীর্ষবিন্দু গ্রাফ হয় এবং c(G)≤२k+१ হয়। যদি সর্বাধিক একটি শীর্ষবিন্দু ছাড়া অন্য সকল শীর্ষবিন্দুর ডিগ্রি কমপক্ষে k≥२ হয়, তাহলে G নিম্নলিখিত গ্রাফগুলির একটির উপগ্রাফ:

१. H-প্রকার গ্রাফ: H(२k+१,२k+१,k) এবং H(n,२k+२,k) (n≥२k+२) २. F-প্রকার গ্রাফ: F(s,t,k) (s≥१,t≥१) এবং F₁(t,k) (t≥१)
३. বিশেষ ছোট গ্রাফ:

K₂+Mₜ (t≥६)
K₂+(Sₛ∪Mₜ) (s+t≥६, যখন k=३)
K₃+Mₜ (t≥७, যখন k=४)

অনুসিদ্ধান্ত এবং প্রয়োগ

উপপাদ্য ३.३ (পথ সংস্করণ)

সংযুক্ত গ্রাফের জন্য, min{n,२k+३} দৈর্ঘ্যের পথ ধারণ না করা গ্রাফের সম্পূর্ণ বর্ণনা প্রদান করা।

উপপাদ্য ३.५ (চরম গ্রাফ প্রয়োগ)

{Sₖ₊२,P२ₖ₊१}-মুক্ত গ্রাফের চরম গ্রাফ সর্বাধিক २k ক্রম সহ সংযুক্ত উপাদান নিয়ে গঠিত প্রমাণ করা।

অ্যালগরিদম ফলাফল

O(kn) সময় জটিলতার সাথে অ্যালগরিদম প্রদান করা, যা গ্রাফে कमपक्ष २k+२ দৈর্ঘ্যের চক्र রয়েছে কিনা তা নির্ধারণ করে।

१. বন্ডি উপপাদ্যের স্থিতিশীলতা সমস্যা সম্পূর্ণভাবে সমাধান করা, সমস্ত চরম গ্রাফের নির্ভুল বর্ণনা প্রদান করা २. একাধিক ক্লাসিক্যাল ফলাফল একীভূত করা, তত্ত্বের অভ্যন্তরীণ সংযোগ প্রদর্শন করা ३. সম্পর্কিত অ্যালগরিদম সমস্যার জন্য কার্যকর সমাধান প্রদান করা

সীমাবদ্ধতা

१. প্যারামিটার সীমাবদ্ধতা: k≥२ প্রয়োজন, ছোট প্যারামিটার ক্ষেত্রে বিশেষ পরিচালনা প্রয়োজন २. २-সংযোগযোগ্যতা অনুমান: পদ্ধতি গ্রাফের २-সংযোগযোগ্যতার উপর গুরুতরভাবে নির্ভর করে ३. অ-গঠনমূলক: যদিও অ্যালগরিদম প্রদান করা হয়েছে, প্রধান ফলাফল অস্তিত্ব উপপাদ্য

ভবিষ্যত দিকনির্দেশনা

१. আরও সাধারণ গ্রাফ শ্রেণীতে সম্প্রসারণ: অ-२-সংযুক্ত গ্রাফের ক্ষেত্রে গবেষণা করা २. প্যারামিটার অপ্টিমাইজেশন: ডিগ্রি শর্ত বা চক্র দৈর্ঘ্য নিম্ন সীমা আরও উন্নত করা ३. অ্যালগরিদম উন্নতি: আরও দক্ষ নির্ধারণ অ্যালগরিদম বিকাশ করা ४. প্রয়োগ সম্প্রসারণ: অন্যান্য গ্রাফ তত্ত্ব সমস্যায় স্থিতিশীলতা পদ্ধতি প্রয়োগ করা

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক গভীরতা: একটি কঠিন চরম গ্রাফ তত্ত্ব সমস্যা সম্পূর্ণভাবে সমাধান করা, প্রযুক্তিগত প্রয়োজনীয়তা অত্যন্ত উচ্চ २. পদ্ধতিগত উদ্ভাবন: "পথ দ্রাক্ষালতা" কৌশলের প্রয়োগ নতুন প্রমাণ চিন্তাভাবনা প্রদর্শন করে ३. ফলাফল সম্পূর্ণতা: শুধুমাত্র প্রধান উপপাদ্য প্রমাণ করা নয়, বরং সমৃদ্ধ অনুসিদ্ধান্ত এবং প্রয়োগ প্রদান করা ४. আন্তঃশৃঙ্খলা প্রভাব: চরম গ্রাফ তত্ত্ব, বর্ণালী গ্রাফ তত্ত্ব এবং অ্যালগরিদমিক গ্রাফ তত্ত্ব সংযোগ করা

অপূর্ণতা

१. প্রমাণ জটিলতা: কেস বিশ্লেষণ অত্যন্ত জটিল, সম্ভবত আরও সংক্ষিপ্ত প্রমাণ পদ্ধতি বিদ্যমান २. পাঠযোগ্যতা: প্রযুক্তিগত বিবরণ অনেক বেশি, অ-বিশেষজ্ঞ পাঠকদের জন্য যথেষ্ট বন্ধুত্বপূর্ণ নয় ३. ব্যবহারিক প্রয়োগ: যদিও অ্যালগরিদম প্রয়োগ রয়েছে, ব্যবহারিক মূল্য সীমিত

প্রভাব

१. তাত্ত্বিক অবদান: চরম গ্রাফ তত্ত্বের জন্য গুরুত্বপূর্ণ স্থিতিশীলতা ফলাফল প্রদান করা २. পদ্ধতিগত মূল্য: প্রমাণ কৌশল অন্যান্য অনুরূপ সমস্যায় প্রয়োগ করা যেতে পারে ३. পরবর্তী গবেষণা: ইতিমধ্যে একাধিক পরবর্তী পত্র দ্বারা উদ্ধৃত এবং উন্নত করা হয়েছে

প্রযোজ্য পরিস্থিতি

१. তাত্ত্বিক গবেষণা: চরম গ্রাফ তত্ত্ব, কাঠামোগত গ্রাফ তত্ত্বের গবেষণা २. অ্যালগরিদম ডিজাইন: গ্রাফে দীর্ঘ চক্র সনাক্তকরণ অ্যালগরিদমের তাত্ত্বিক ভিত্তি ३. বর্ণালী গ্রাফ তত্ত্ব: বর্ণালী পদ্ধতির পরিপূরক হাতিয়ার হিসাবে

তথ্যসূত্র

পত্রটি ২८টি গুরুত্বপূর্ণ তথ্যসূত্র উদ্ধৃত করে, যা অন্তর্ভুক্ত করে:

ক্লাসিক্যাল ফলাফল: ডিরাক, বন্ডি, ভস্ এবং অন্যদের মৌলিক কাজ
সাম্প্রতিক উন্নয়ন: ফোমিন এবং অন্যদের অ্যালগরিদম গবেষণা, ফিউরেডি এবং অন্যদের স্থিতিশীলতা তত্ত্ব
সম্পর্কিত ক্ষেত্র: বর্ণালী গ্রাফ তত্ত্ব, টুরান তত্ত্বের সম্পর্কিত কাজ

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক গণিত পত্র, যা একটি গুরুত্বপূর্ণ চরম গ্রাফ তত্ত্ব সমস্যা সম্পূর্ণভাবে সমাধান করে। যদিও প্রযুক্তিগতভাবে শক্তিশালী, তাত্ত্বিক অবদান উল্লেখযোগ্য, পদ্ধতি উদ্ভাবনী, এবং ফলাফল সম্পূর্ণ। পত্রটি শুধুমাত্র চরম গ্রাফ তত্ত্বের উন্নয়ন এগিয়ে নিয়ে যায় না, বরং সম্পর্কিত অ্যালগরিদম এবং প্রয়োগ সমস্যার জন্য তাত্ত্বিক সহায়তা প্রদান করে।