2025-11-17T15:31:13.202496

Remoteness, order, size and connectivity constraints in digraphs

Mallu
Let \( D \) be a strongly connected digraph. The average distance of a vertex \( v \) in \( D \) is defined as the arithmetic mean of the distances from \( v \) to all other vertices in \( D \). The remoteness \( ρ(D) \) of \( D \) is the maximum of the average distances of the vertices in \( D \). In this paper, we provide a sharp upper bound on the remoteness of a strong digraph with given order, size, and vertex-connectivity. We then characterise the extremal digraphs that maximise remoteness among all strong digraphs of order \(n\), size at least \(m\), and vertex-connectivity \(κ\). Finally, we demonstrate that the upper bounds on the remoteness of a graph given its order, size, and connectivity constraints (see \cite{DanMafMal2025}) can be extended to a larger class of digraphs containing all graphs, the Eulerian digraphs.
academic

দিগ্রাফে দূরত্ব, ক্রম, আকার এবং সংযোগযোগ্যতা সীমাবদ্ধতা

মৌলিক তথ্য

  • পেপার আইডি: 2510.08841
  • শিরোনাম: Remoteness, order, size and connectivity constraints in digraphs
  • লেখক: Sufiyan Mallu (জোহানেসবার্গ বিশ্ববিদ্যালয়, দক্ষিণ আফ্রিকা)
  • শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
  • প্রকাশনার সময়: অক্টোবর ১৩, ২০২৫ (arXiv প্রাক-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.08841

সারসংক্ষেপ

এই পেপারটি দৃঢ়ভাবে সংযুক্ত দিগ্রাফের দূরত্ব (remoteness) সমস্যা অধ্যয়ন করে। দৃঢ়ভাবে সংযুক্ত দিগ্রাফ DD এর জন্য, শীর্ষবিন্দু vv এর গড় দূরত্ব vv থেকে অন্য সকল শীর্ষবিন্দুর দূরত্বের গাণিতিক গড় হিসাবে সংজ্ঞায়িত করা হয়, যখন DD এর দূরত্ব ρ(D)\rho(D) সকল শীর্ষবিন্দুর গড় দূরত্বের সর্বোচ্চ মান হিসাবে সংজ্ঞায়িত করা হয়। পেপারটি প্রদত্ত ক্রম, আকার এবং শীর্ষবিন্দু সংযোগযোগ্যতার দৃঢ় দিগ্রাফের দূরত্বের কঠোর উপরের সীমা প্রদান করে, সকল ক্রম nn, আকার কমপক্ষে mm, এবং শীর্ষবিন্দু সংযোগযোগ্যতা κ\kappa এর দৃঢ় দিগ্রাফের মধ্যে দূরত্ব সর্বাধিক করে এমন চরম দিগ্রাফ চিহ্নিত করে, এবং প্রমাণ করে যে অনির্দেশিত গ্রাফের ক্রম, আকার এবং সংযোগযোগ্যতা সীমাবদ্ধতা সম্পর্কিত দূরত্বের উপরের সীমা সকল গ্রাফ ধারণকারী বৃহত্তর দিগ্রাফ শ্রেণী—অয়লার দিগ্রাফে সাধারণীকৃত করা যায়।

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

  1. গবেষণা সমস্যা: যদিও গ্রাফে দূরত্ব সমস্যা ব্যাপকভাবে অধ্যয়ন করা হয়েছে, দিগ্রাফে দূরত্বের গবেষণা তুলনামূলকভাবে অপর্যাপ্ত, বিশেষত নৈকট্য (proximity) এবং দূরত্ব ধারণার দিগ্রাফে অন্বেষণ এখনও গভীর নয়।
  2. সমস্যার গুরুত্ব:
    • দূরত্ব পরামিতি গ্রাফ তত্ত্বে মৌলিক অবস্থান রাখে, নেটওয়ার্ক বিশ্লেষণ, অ্যালগরিদম ডিজাইন ইত্যাদি ক্ষেত্রে গুরুত্বপূর্ণ প্রয়োগ রয়েছে
    • দিগ্রাফ বাস্তব বিশ্বের অ-প্রতিসম সম্পর্ক আরও সঠিকভাবে মডেল করতে পারে, যেমন পরিবহন নেটওয়ার্ক, সামাজিক নেটওয়ার্ক ইত্যাদি
    • সংযোগযোগ্যতা সীমাবদ্ধতার অধীনে চরম সমস্যা উল্লেখযোগ্য তাত্ত্বিক মূল্য রাখে
  3. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
    • Ai এবং অন্যরা 1 প্রথমবার নৈকট্য এবং দূরত্ব ধারণা দিগ্রাফে প্রসারিত করেছেন, কিন্তু সম্পর্কিত গবেষণা এখনও সীমিত
    • বিদ্যমান ফলাফল প্রধানত শুধুমাত্র ক্রম সীমাবদ্ধতা বিবেচনা করার ক্ষেত্রে কেন্দ্রীভূত, আকার এবং সংযোগযোগ্যতা একযোগে বিবেচনা করার ফলাফল অনুপস্থিত
  4. গবেষণা প্রেরণা: এই পেপারটি দিগ্রাফ দূরত্ব তত্ত্বের ফাঁক পূরণ করতে, আরও নির্ভুল সীমা এবং চরম কাঠামো চিহ্নিত করতে লক্ষ্য রাখে।

মূল অবদান

  1. নতুন উপরের সীমা প্রতিষ্ঠা: প্রদত্ত ক্রম, আকার এবং শীর্ষবিন্দু সংযোগযোগ্যতার অধীনে κ\kappa-সংযুক্ত দৃঢ় দিগ্রাফের দূরত্বের কঠোর উপরের সীমা প্রদান করে
  2. চরম কাঠামো চিহ্নিত করা: দূরত্বের উপরের সীমা অর্জনকারী চরম দিগ্রাফ—κ\kappa-সংযুক্ত পথ সম্পূর্ণ দিগ্রাফ সম্পূর্ণভাবে চিহ্নিত করে
  3. বিদ্যমান ফলাফল সাধারণীকরণ: অনির্দেশিত গ্রাফের দূরত্ব উপরের সীমা অয়লার দিগ্রাফ এই বৃহত্তর গ্রাফ শ্রেণীতে সাধারণীকৃত করা যায় প্রমাণ করে
  4. গঠনমূলক প্রমাণ প্রদান: নির্দিষ্ট চরম গ্রাফ পরিবার নির্মাণের মাধ্যমে, প্রাপ্ত সীমার কঠোরতা প্রমাণ করে

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

কাজের সংজ্ঞা

ইনপুট: দৃঢ়ভাবে সংযুক্ত দিগ্রাফ DD এবং এর পরামিতি (ক্রম nn, আকার mm, শীর্ষবিন্দু সংযোগযোগ্যতা κ\kappa) আউটপুট: দূরত্ব ρ(D)\rho(D) এর উপরের সীমা সীমাবদ্ধতা: DD অবশ্যই κ\kappa-সংযুক্ত দৃঢ় দিগ্রাফ হতে হবে

মূল ধারণা

  1. গড় দূরত্ব: শীর্ষবিন্দু vv এর গড় দূরত্ব সংজ্ঞায়িত করা হয় যেমন σ(v,D)=1n−1∑w∈V(D)dD(v,w)\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)
  2. দূরত্ব: দিগ্রাফের দূরত্ব সংজ্ঞায়িত করা হয় যেমন ρ(D)=max⁡v∈V(D)σ(v,D)\rho(D) = \max_{v \in V(D)} \sigma(v,D)
  3. κ\kappa-সংযুক্ত পথ সম্পূর্ণ দিগ্রাফ: ফর্মের দিগ্রাফ K1+←[Kκ↔]ℓ+←Ka↔+←Kb↔K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b} যেখানে a≥κa \geq \kappa।

প্রধান প্রযুক্তিগত পদ্ধতি

  1. চরম বিশ্লেষণ: দূরত্ব সর্বাধিক করে এমন শীর্ষবিন্দুর দূরত্ব বিতরণ বিশ্লেষণের মাধ্যমে, কাঠামো সীমাবদ্ধতা প্রতিষ্ঠা করে
  2. আবেগপূর্ণ নির্মাণ: ধাপে ধাপে প্রমাণ করে যে চরম গ্রাফ নির্দিষ্ট পথ সম্পূর্ণ কাঠামো থাকতে হবে
  3. আকার অপ্টিমাইজেশন: স্থির দূরত্বের অধীনে, গ্রাফের সর্বাধিক আকার সীমাবদ্ধতা বিশ্লেষণ করে

মূল লেম্মা

লেম্মা ৩.১:

  • (ক) κ\kappa-সংযুক্ত পথ সম্পূর্ণ দিগ্রাফ HH এর জন্য, যেকোনো চাপ যোগ করা এর দূরত্ব হ্রাস করে
  • (খ) দুটি ভিন্ন κ\kappa-সংযুক্ত পথ সম্পূর্ণ দৃঢ় দিগ্রাফের মধ্যে কঠোর আকার-দূরত্ব বাণিজ্য-বন্ধ সম্পর্ক বিদ্যমান
  • (গ) প্রদত্ত n,κn, \kappa, নির্দিষ্ট আকারের κ\kappa-সংযুক্ত পথ সম্পূর্ণ দৃঢ় দিগ্রাফের অস্তিত্বের প্রয়োজনীয় এবং পর্যাপ্ত শর্ত

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

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

প্রমাণ কৌশল

  1. অস্তিত্ব প্রমাণ: নির্দিষ্ট চরম গ্রাফ পরিবার নির্মাণ করে
  2. অনন্যতা প্রমাণ: চরম গ্রাফের কাঠামো অনন্যতা প্রমাণ করে
  3. কঠোরতা যাচাইকরণ: নির্দিষ্ট উদাহরণের মাধ্যমে সীমার কঠোরতা যাচাই করে

প্রধান ফলাফল

মূল উপপাদ্য

উপপাদ্য ৩.২: ধরুন DD ক্রম nn, আকার mm এর κ\kappa-সংযুক্ত দৃঢ় দিগ্রাফ, যেখানে m≤n2−2n−1m \leq n^2 - 2n - 1, তাহলে ρ(D)≤ρ(DPKn,m,κ)\rho(D) \leq \rho(DPK_{n,m,\kappa})

যখন m≡(n2−2n−1)(modκ)m \equiv (n^2-2n-1) \pmod{\kappa} এবং নির্দিষ্ট শর্ত সন্তুষ্ট হয়, সমতা ধারণ করে যদি এবং শুধুমাত্র যদি D=DPKn,m,κD = DPK_{n,m,\kappa}।

নির্দিষ্ট সীমা

অনুসিদ্ধান্ত ৩.৩: উপযুক্ত শর্তে, ρ(D)≤nκ+2−1κ−κ−1n−1−m∗κ(n−1)\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}

যেখানে m∗m^* হল m∗≥mm^* \geq m এবং m∗≡(n2−2n−1)(modκ)m^* \equiv (n^2-2n-1) \pmod{\kappa} সন্তুষ্ট করে এমন ক্ষুদ্রতম পূর্ণসংখ্যা।

অয়লার দিগ্রাফের ফলাফল

উপপাদ্য ৪.৩: ধরুন DD ক্রম nn, আকার কমপক্ষে 2m02m_0 এর κ\kappa-সংযুক্ত অয়লার দিগ্রাফ, তাহলে ρ(D)≤n2κ+2−1κ−κ−1n−1−m0κ(n−1)\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}

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

  1. কাঠামো চিহ্নিতকরণের সম্পূর্ণতা: শুধুমাত্র উপরের সীমা প্রদান করে না, বরং উপরের সীমা অর্জনকারী চরম কাঠামো সম্পূর্ণভাবে চিহ্নিত করে
  2. বহু-পরামিতি সীমাবদ্ধতার পরিচালনা: ক্রম, আকার এবং সংযোগযোগ্যতা তিনটি পরামিতির সীমাবদ্ধতা একযোগে বিবেচনা করে
  3. অনির্দেশিত গ্রাফ থেকে দিগ্রাফে সাধারণীকরণ: অয়লার দিগ্রাফের বৈশিষ্ট্য চতুরভাবে ব্যবহার করে, অনির্দেশিত গ্রাফের ফলাফল দিগ্রাফে সাধারণীকৃত করে
  4. মডুলার অপারেশন শর্তের প্রবর্তন: আকার পরামিতি অবশ্যই সন্তুষ্ট করতে হবে এমন মডুলার অপারেশন শর্ত আবিষ্কার করে

সম্পর্কিত কাজ

ঐতিহাসিক উন্নয়ন

  1. Zelinka 29 এবং Aouchiche, Hansen 4: সংযুক্ত গ্রাফের দূরত্বের মৌলিক উপরের সীমা প্রতিষ্ঠা করেছেন ρ(G)≤n/2\rho(G) \leq n/2
  2. Ai এবং অন্যরা 1: দূরত্ব ধারণা দিগ্রাফে সাধারণীকৃত করেছেন
  3. Entringer এবং অন্যরা 18: গ্রাফের আকার সীমাবদ্ধতা বিবেচনা করেছেন
  4. Dankelmann এবং অন্যরা 15: সংযোগযোগ্যতা সীমাবদ্ধতা সহ অনির্দেশিত গ্রাফের দূরত্ব সীমা প্রতিষ্ঠা করেছেন

এই পেপারের অবদানের অবস্থান

এই পেপারটি দিগ্রাফ দূরত্ব বিশেষভাবে অধ্যয়ন করা দ্বিতীয় পেপার, দিগ্রাফ তত্ত্বে গুরুত্বপূর্ণ ফাঁক পূরণ করে, এবং সফলভাবে অনির্দেশিত গ্রাফের নির্ভুল ফলাফল বৃহত্তর দিগ্রাফ শ্রেণীতে সাধারণীকৃত করেছে।

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

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

  1. κ\kappa-সংযুক্ত দৃঢ় দিগ্রাফের দূরত্বের কঠোর উপরের সীমা প্রতিষ্ঠা করেছে
  2. চরম গ্রাফের কাঠামো সম্পূর্ণভাবে চিহ্নিত করেছে (κ\kappa-সংযুক্ত পথ সম্পূর্ণ দিগ্রাফ)
  3. অনির্দেশিত গ্রাফের দূরত্ব সীমা অয়লার দিগ্রাফে সাধারণীকৃত করা যায় প্রমাণ করেছে

তাত্ত্বিক তাৎপর্য

  • দিগ্রাফের দূরত্ব তত্ত্ব সমৃদ্ধ করেছে
  • নেটওয়ার্ক বিশ্লেষণের জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করেছে
  • অনির্দেশিত গ্রাফ এবং দিগ্রাফ তত্ত্বের মধ্যে সেতু প্রতিষ্ঠা করেছে

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

  1. আরও সাধারণ দিগ্রাফ শ্রেণীর দূরত্ব অধ্যয়ন করা
  2. দূরত্ব এবং অন্যান্য গ্রাফ পরামিতির সম্পর্ক অন্বেষণ করা
  3. ভারযুক্ত দিগ্রাফের ক্ষেত্রে বিবেচনা করা

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

সুবিধা

  1. তাত্ত্বিক সম্পূর্ণতা: শুধুমাত্র সীমা প্রদান করে না, বরং চরম কাঠামো সম্পূর্ণভাবে চিহ্নিত করে
  2. প্রযুক্তিগত গভীরতা: প্রমাণ কৌশল সূক্ষ্ম, বিশেষত দিগ্রাফের জটিলতা পরিচালনায়
  3. ফলাফলের কঠোরতা: সকল প্রধান ফলাফল কঠোর, সীমা সর্বোত্তম তা নির্দেশ করে
  4. সাধারণীকরণের চতুরতা: অয়লার দিগ্রাফের মাধ্যমে অনির্দেশিত গ্রাফ ফলাফল দিগ্রাফে সাধারণীকৃত করার পদ্ধতি অত্যন্ত সৃজনশীল

অসুবিধা

  1. প্রয়োগের পরিসীমা: প্রধানত তাত্ত্বিক ফলাফল, ব্যবহারিক প্রয়োগ মূল্য আরও অন্বেষণের প্রয়োজন
  2. গণনামূলক জটিলতা: সম্পর্কিত সমস্যার গণনামূলক জটিলতা আলোচনা করা হয়নি
  3. পরামিতি পরিসীমা: কিছু ফলাফল নির্দিষ্ট মডুলার অপারেশন শর্ত সন্তুষ্ট করতে প্রয়োজন, প্রয়োগযোগ্যতা সীমিত করে

প্রভাব

  1. তাত্ত্বিক অবদান: দিগ্রাফ দূরত্ব তত্ত্বের জন্য গুরুত্বপূর্ণ ভিত্তি স্থাপন করেছে
  2. পদ্ধতিগত মূল্য: প্রমাণ কৌশল অন্যান্য দিগ্রাফ সমস্যায় প্রয়োগযোগ্য হতে পারে
  3. পরবর্তী গবেষণা: দিগ্রাফের অন্যান্য দূরত্ব পরামিতি অধ্যয়নের জন্য কাঠামো প্রদান করে

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

  1. নেটওয়ার্ক বিশ্লেষণে কেন্দ্রীয়তা পরিমাপ
  2. দিগ্রাফের কাঠামো বিশ্লেষণ
  3. চরম গ্রাফ তত্ত্ব গবেষণা
  4. অ্যালগরিদম ডিজাইনে তাত্ত্বিক সীমা বিশ্লেষণ

সংদর্ভ

পেপারটি গ্রাফ তত্ত্বে দূরত্ব সমস্যার প্রধান গবেষণা ফলাফল অন্তর্ভুক্ত করে ২৯টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, বিশেষত:

  • 1 Ai এবং অন্যদের দিগ্রাফ নৈকট্য এবং দূরত্বের যুগান্তকারী কাজ
  • 15 Dankelmann এবং অন্যদের অনির্দেশিত গ্রাফ দূরত্বের সর্বশেষ ফলাফল
  • 29 Zelinka এর দূরত্ব সম্পর্কিত প্রাথমিক কাজ

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চমানের তাত্ত্বিক পেপার, দিগ্রাফ দূরত্ব এই গুরুত্বপূর্ণ কিন্তু তুলনামূলকভাবে নতুন গবেষণা ক্ষেত্রে বাস্তবসম্মত অবদান রাখে। পেপারটির প্রযুক্তিগত স্তর উচ্চ, ফলাফল সম্পূর্ণ এবং কঠোর, এই ক্ষেত্রের পরবর্তী গবেষণার জন্য দৃঢ় ভিত্তি স্থাপন করে।