2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

দূরত্ব পারস্পরিক-দৃশ্যমানতা রঙায়ন: (সম্পূর্ণ) আধিপত্য, নির্ভুল দূরত্ব গ্রাফ এবং গ্রাফ পণ্যের সাথে সম্পর্ক

মৌলিক তথ্য

  • পত্রের আইডি: 2510.10284
  • শিরোনাম: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • লেখক: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
  • প্রকাশনা সময়: ২০২৫ সালের অক্টোবর ১১ তারিখ
  • পত্রের লিঙ্ক: https://arxiv.org/abs/2510.10284

সারসংক্ষেপ

এই পত্রটি k-দূরত্ব পারস্পরিক-দৃশ্যমানতা রঙায়ন সমস্যা অধ্যয়ন করে, যা ডি স্টেফানো দ্বারা ২০২২ সালে প্রবর্তিত পারস্পরিক-দৃশ্যমানতা ধারণার একটি সম্প্রসারণ। গ্রাফ G এর শীর্ষবিন্দু উপসেট S এর জন্য, যদি S তে যেকোনো দুটি শীর্ষবিন্দুর মধ্যে সর্বাধিক k দৈর্ঘ্যের একটি জিওডেসিক বিদ্যমান থাকে এবং এর অভ্যন্তরীণ শীর্ষবিন্দুগুলি S তে না থাকে, তাহলে S কে k-দূরত্ব পারস্পরিক-দৃশ্যমানতা সেট (k-DMV সেট) বলা হয়। পত্রটি এই ধারণাটিকে পারস্পরিক-দৃশ্যমানতা রঙায়নের সাথে একত্রিত করে, k-DMV রঙায়ন সংখ্যা χ_μ_k(G) সংজ্ঞায়িত করে। গবেষণায় দেখা গেছে যে k=2 হলে সবচেয়ে আকর্ষণীয় ফলাফল পাওয়া যায়, χ_μ_2(G) ≤ |V(G)|/2 প্রমাণ করা হয়েছে, এবং আধিপত্য সংখ্যা, সম্পূর্ণ আধিপত্য সংখ্যা এবং নির্ভুল দূরত্ব গ্রাফের সাথে গভীর সংযোগ স্থাপন করা হয়েছে।

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

  1. সমস্যার উৎস: পারস্পরিক-দৃশ্যমানতা ধারণা মূলত ডি স্টেফানো দ্বারা ২০২২ সালে প্রস্তাব করা হয়েছিল, যা ক্লাসিক্যাল "তিন বিন্দু সহরেখীয় নয়" সমস্যা এবং সমতল চলমান রোবট পুনর্স্থাপন সমস্যার সাথে সম্পর্কিত।
  2. গবেষণা প্রেরণা:
    • পারস্পরিক-দৃশ্যমানতা ধারণা যদিও নতুন, তবে ব্যাপক মনোযোগ আকর্ষণ করেছে (MathSciNet-এ ইতিমধ্যে ২০টিরও বেশি উদ্ধৃতি রয়েছে)
    • বিদ্যমান গবেষণা প্রধানত পারস্পরিক-দৃশ্যমানতা সেটের সর্বাধিক মূলত্বের উপর দৃষ্টি নিবদ্ধ করে, রঙায়ন সমস্যার সিস্টেমেটিক অধ্যয়ন অনুপস্থিত
    • k-দূরত্ব সীমাবদ্ধতা যোগাযোগকে আরও দক্ষ করে তোলে এবং ব্যবহারিক প্রয়োগ মূল্য রয়েছে
  3. ব্যবহারিক তাৎপর্য: কম্পিউটার নেটওয়ার্ক বা সামাজিক নেটওয়ার্কে, পারস্পরিক-দৃশ্যমানতা সম্পত্তি সহ শীর্ষবিন্দুগুলি দক্ষ, গোপনীয় যোগাযোগের প্রয়োজন এমন সত্তাগুলিকে প্রতিনিধিত্ব করতে পারে, যা নিশ্চিত করে যে বার্তা অন্য কোনো সত্তার মাধ্যমে প্রেরণ করা হয় না।

মূল অবদান

  1. নতুন ধারণা প্রবর্তন: প্রথমবারের মতো k-দূরত্ব পারস্পরিক-দৃশ্যমানতা রঙায়ন সংখ্যা χ_μ_k(G) সংজ্ঞায়িত করা হয়েছে, যা দল কভারেজ সংখ্যা (k=1) এবং পারস্পরিক-দৃশ্যমানতা রঙায়ন সংখ্যা (k≥diam(G)) কে একীভূত করে
  2. মৌলিক সীমানা স্থাপন:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ প্রমাণ করা হয়েছে এবং এই সীমানা অর্জনকারী গ্রাফ পরিবার প্রদান করা হয়েছে
    • বিচ্ছিন্ন শীর্ষবিন্দু ছাড়া গ্রাফের জন্য, χ_μ_2(G) ≤ γ_t(G)
    • কমপক্ষে ৭ পরিধি সহ গ্রাফের জন্য, χ_μ_2(G) ≥ γ(G)
  3. নির্ভুল দূরত্ব গ্রাফের সাথে সংযোগ আবিষ্কার: বিচ্ছিন্ন শীর্ষবিন্দু ছাড়া এবং কমপক্ষে ৭ পরিধি সহ গ্রাফ G এর জন্য, θ(G♮2) = γ_t(G) প্রমাণ করা হয়েছে
  4. গ্রাফ পণ্যের সিস্টেমেটিক অধ্যয়ন:
    • অভিধান ক্রম পণ্য: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • শক্তিশালী পণ্য: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • কার্টেসিয়ান পণ্য: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. বিশেষ গ্রাফ শ্রেণীর বৈশিষ্ট্য: χ_μ_k(G) = χ_μ(G) (যেখানে k = diam(G)-1) সন্তুষ্ট করে এমন ব্লক গ্রাফগুলি সম্পূর্ণভাবে চিহ্নিত করা হয়েছে

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

কাজের সংজ্ঞা

গ্রাফ G এবং ধনাত্মক পূর্ণসংখ্যা k দেওয়া হলে, k-দূরত্ব পারস্পরিক-দৃশ্যমানতা রঙায়ন হল V(G) কে বেশ কয়েকটি k-DMV সেটে বিভক্ত করার একটি রঙায়ন স্কিম। যেখানে k-DMV সেট M সন্তুষ্ট করে: M তে যেকোনো দুটি শীর্ষবিন্দু u,v এর জন্য, সর্বাধিক k দৈর্ঘ্যের একটি u,v-জিওডেসিক বিদ্যমান থাকে যার অভ্যন্তরীণ শীর্ষবিন্দু M তে নেই।

ইনপুট: গ্রাফ G = (V,E), ধনাত্মক পূর্ণসংখ্যা k আউটপুট: V(G) এর একটি বিভাজন {S_1, S_2, ..., S_t}, যেখানে প্রতিটি S_i একটি k-DMV সেট উদ্দেশ্য: বিভাজনের সেট সংখ্যা t কে ন্যূনতম করা

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

১. মৌলিক তত্ত্ব প্রতিষ্ঠা

পর্যবেক্ষণ ১: ব্যাস d সহ গ্রাফ G এর জন্য, একটি একঘেয়ে শৃঙ্খল রয়েছে: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

পর্যবেক্ষণ ২: মৌলিক নিম্ন সীমানা χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

২. k=2 ক্ষেত্রের গভীর বিশ্লেষণ

উপপাদ্য ৪: যেকোনো সংযুক্ত গ্রাফ G এর জন্য, χ_μ_2(G) ≤ ⌈n/2⌉

প্রমাণের কৌশল: উৎপন্ন গাছের উপর আবেগপূর্ণ নির্মাণের মাধ্যমে, গাছটিকে দুটি রঙ দিয়ে রঙায়ন করা যায় এমন কাঠামোতে বিভক্ত করা।

উপপাদ্য ৫: যদি G এর কোনো বিচ্ছিন্ন শীর্ষবিন্দু না থাকে, তাহলে χ_μ_2(G) ≤ γ_t(G)

প্রমাণ পদ্ধতি: গঠনমূলক প্রমাণ, সম্পূর্ণ আধিপত্য সেট D = {v_1,...,v_γ_t(G)} ব্যবহার করে, D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j) সংজ্ঞায়িত করে, প্রতিটি D_i একটি 2DMV সেট প্রমাণ করা।

৩. পরিধি এবং আধিপত্য সংখ্যার সম্পর্ক

লেম্মা ৬: যদি g(G) ≥ 7 হয়, তাহলে χ_μ_2(G)-রঙায়নে প্রতিটি রঙ শ্রেণী C কোনো শীর্ষবিন্দুর বন্ধ প্রতিবেশীর একটি উপসেট।

উপপাদ্য ৭: যদি g(G) ≥ 7 হয়, তাহলে χ_μ_2(G) ≥ γ(G)

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

  1. একীভূত কাঠামো: দল কভারেজ, পারস্পরিক-দৃশ্যমানতা রঙায়ন কে k-DMV রঙায়ন কাঠামোতে একীভূত করা
  2. পরিধি শর্তের নির্ভুল বৈশিষ্ট্য: পরিধি ৭ χ_μ_2(G) ≥ γ(G) নিশ্চিত করার ন্যূনতম মান প্রমাণ করা
  3. নির্ভুল দূরত্ব গ্রাফ সংযোগ: প্রথমবারের মতো 2DMV রঙায়ন এবং নির্ভুল দূরত্ব-২ গ্রাফের মধ্যে গভীর সংযোগ স্থাপন করা
  4. গ্রাফ পণ্যের সিস্টেমেটিক বিশ্লেষণ: তিনটি প্রধান গ্রাফ পণ্যের জন্য কঠোর উপরের এবং নিম্ন সীমানা প্রদান করা

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

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

এই পত্রটি প্রধানত তাত্ত্বিক প্রমাণ পদ্ধতি ব্যবহার করে, সীমানার কঠোরতা যাচাই করার জন্য নির্দিষ্ট গ্রাফ পরিবার নির্মাণের মাধ্যমে:

  1. পথ এবং চক্র: P_n এবং C_n এর নির্ভুল χ_μ_k মান গণনা করা হয়েছে
  2. বিশেষ গ্রাফ পরিবার: বিভিন্ন সীমানা অর্জনকারী গ্রাফ পরিবার নির্মাণ করা হয়েছে
  3. পণ্য গ্রাফ: P_n⊠K_m ইত্যাদি নির্দিষ্ট পণ্য গ্রাফের বৈশিষ্ট্য বিশ্লেষণ করা হয়েছে

মূল উদাহরণ বিশ্লেষণ

প্রস্তাব ২:

  • পথ P_n এর জন্য: χ_μ_k(P_n) = ⌈n/2⌉
  • চক্র C_n এর জন্য: χ_μ_k(C_n) = ⌈n/3⌉ (যখন n ≤ 3k), ⌈n/2⌉ (অন্যথায়)

প্রস্তাব ১२: P_n⊠K_m এর জন্য (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

  1. মৌলিক সীমানার কঠোরতা:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ সকল গ্রাফের জন্য সত্য, এবং পথ, দীর্ঘ চক্র ইত্যাদি দ্বারা অর্জিত
    • χ_μ_2(G) ≤ γ_t(G) বিচ্ছিন্ন শীর্ষবিন্দু ছাড়া গ্রাফের জন্য সত্য, এবং পার্থক্য যেকোনো বড় করা যায় এমন গ্রাফ পরিবার নির্মাণ করা যায়
  2. পরিধি শর্তের সর্বোত্তমতা:
    • পরিধি ৬ কিন্তু γ(G) = 5 > χ_μ_2(G) = 3 সহ প্রতিউদাহরণ নির্মাণ করা হয়েছে
    • পরিধি ৭ χ_μ_2(G) ≥ γ(G) নিশ্চিত করার ন্যূনতম শর্ত প্রমাণ করা হয়েছে
  3. গ্রাফ পণ্য ফলাফলের তীক্ষ্ণতা:
    • শক্তিশালী পণ্য সীমানা χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) অসীম গ্রাফ পরিবার দ্বারা অর্জিত
    • কার্টেসিয়ান পণ্য নিম্ন সীমানা টোরাস গ্রাফ ইত্যাদি দ্বারা অর্জিত

নির্ভুল দূরত্ব গ্রাফের আশ্চর্যজনক সংযোগ

উপপাদ্য ৮: যদি G এর কোনো বিচ্ছিন্ন শীর্ষবিন্দু না থাকে এবং g(G) ≥ 7 হয়, তাহলে θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

এই ফলাফল তিনটি আপাতদৃষ্টিতে অসম্পর্কিত গ্রাফ পরামিতির মধ্যে একটি সমতা সম্পর্ক স্থাপন করে, যার গুরুত্বপূর্ণ তাত্ত্বিক তাৎপর্য রয়েছে।

হাইপারকিউবের বিশেষ বৈশিষ্ট্য

প্রস্তাব ১६: n-হাইপারকিউব Q_n এর জন্য, χ_μ_2(Q_n) ≤ γ(Q_n)

অনুমান: χ_μ_2(Q_n) = γ(Q_n) সকল n এর জন্য সত্য

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

  1. পারস্পরিক-দৃশ্যমানতা গবেষণা: ডি স্টেফানো (২০२२) মৌলিক ধারণা প্রবর্তন করেছেন, সেরা ইত্যাদি k-দূরত্ব সংস্করণে সম্প্রসারিত করেছেন
  2. পারস্পরিক-দৃশ্যমানতা রঙায়ন: ক্লাভজার ইত্যাদি (२०२५) প্রথম পারস্পরিক-দৃশ্যমানতা রঙায়ন সমস্যা অধ্যয়ন করেছেন
  3. নির্ভুল দূরত্ব গ্রাফ: ১৯८०-এর দশকে প্রবর্তিত, সম্প্রতি পুনরায় মনোযোগ আকর্ষণ করছে
  4. আধিপত্য তত্ত্ব: ক্লাসিক্যাল গ্রাফ তত্ত্ব গবেষণা ক্ষেত্র, এই পত্রটি নতুন সংযোগ স্থাপন করেছে

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

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

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

সীমাবদ্ধতা

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

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

পত্রটি তিনটি নির্দিষ্ট উন্মুক্ত সমস্যা প্রস্তাব করেছে:

সমস্যা ১: χ_μ_2(G) = θ(G) সন্তুষ্ট করে এমন ব্লক গ্রাফ G কে চিহ্নিত করা

সমস্যা २: সংযুক্ত গ্রাফ G,H এর জন্য, কি χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)} সত্য?

সমস্যা ३: কি χ_μ_2(Q_n) = γ(Q_n) সকল হাইপারকিউবের জন্য সত্য?

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

সুবিধা

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

অপূর্ণতা

  1. গণনামূলক জটিলতা অনুপস্থিত: χ_μ_k(G) এর গণনামূলক জটিলতা আলোচনা করা হয়নি
  2. প্রয়োগ সীমাবদ্ধতা: নেটওয়ার্ক যোগাযোগ প্রয়োগ উল্লেখ করা হয়েছে, কিন্তু নির্দিষ্ট প্রয়োগ পরিস্থিতি বিশ্লেষণ অনুপস্থিত
  3. অ্যালগরিদম ডিজাইন: χ_μ_k(G) গণনা বা অনুমান করার জন্য দক্ষ অ্যালগরিদম অনুপস্থিত

প্রভাব

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

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

  1. নেটওয়ার্ক ডিজাইন: যোগাযোগ পথ গোপনীয়তা নিশ্চিত করার প্রয়োজন এমন নেটওয়ার্কে প্রয়োগ
  2. গ্রাফ তত্ত্ব গবেষণা: গ্রাফ কাঠামোগত বৈশিষ্ট্য অধ্যয়নের জন্য নতুন সরঞ্জাম হিসাবে
  3. সমন্বয় অপ্টিমাইজেশন: সম্পর্কিত অপ্টিমাইজেশন সমস্যার জন্য তাত্ত্বিক ভিত্তি প্রদান করে

রেফারেন্স

পত্রটি ১८ টি সম্পর্কিত রেফারেন্স উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

  • ডি স্টেফানো (२०२२): পারস্পরিক-দৃশ্যমানতা ধারণার মূল সাহিত্য
  • সেরা ইত্যাদি: k-দূরত্ব পারস্পরিক-দৃশ্যমানতার সম্প্রসারণ
  • ক্লাভজার ইত্যাদি: পারস্পরিক-দৃশ্যমানতা রঙায়নের প্রথম গবেষণা
  • ক্লাসিক্যাল গ্রাফ তত্ত্ব পাঠ্যপুস্তক এবং আধিপত্য তত্ত্ব সাহিত্য

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