2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনার b-ক্রোমেটিক সংখ্যা নির্ধারণ

মৌলিক তথ্য

  • পেপার আইডি: 2302.13667
  • শিরোনাম: সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনার b-ক্রোমেটিক সংখ্যা নির্ধারণ
  • লেখক: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
  • প্রকাশনার সময়: ২০২৩ সালের ২৭ ফেব্রুয়ারি
  • পেপার লিঙ্ক: https://arxiv.org/abs/2302.13667

সারসংক্ষেপ

ধরা যাক GG এবং HH দুটি গ্রাফ, যার প্রতিটি পথ, চক্র বা তারকা গ্রাফ। এই পেপারটি প্রতিটি সাবডিভিশন-ভার্টেক্স নেইবারহুড করোনা গ্রাফ G⊡HG\boxdot H বা G⊡KnG\boxdot K_n এর b-ক্রোমেটিক সংখ্যা নির্ধারণ করে, যেখানে KnK_n হল nn ক্রমের সম্পূর্ণ গ্রাফ। mm-ডিগ্রি যা n+2n+2 এর চেয়ে বেশি নয় এমন গ্রাফ Kn⊡GK_n\boxdot G এর জন্যও সংশ্লিষ্ট ফলাফল প্রতিষ্ঠিত হয়েছে। সমস্ত প্রমাণ বর্ণনামূলক উদাহরণ সহ সরবরাহ করা হয়েছে।

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

সমস্যার পটভূমি

  1. b-ক্রোমেটিক সংখ্যার ধারণা: Irving এবং Manlove ১৯৯৯ সালে গ্রাফের b-রঙ্গ ধারণা প্রবর্তন করেছিলেন, যা একটি বিশেষ সাধারণ kk-রঙ্গ, যেখানে প্রতিটি রঙের একটি b-শীর্ষ থাকে (যে শীর্ষটি অন্য সমস্ত রঙের শীর্ষের সাথে সংলগ্ন)।
  2. গণনামূলক জটিলতা: গ্রাফের b-ক্রোমেটিক সংখ্যা নির্ধারণ সাধারণ ক্ষেত্রে NP-কঠিন সমস্যা, কিন্তু গাছের জন্য বহুপদী সময়ে সমাধানযোগ্য।
  3. গ্রাফ পণ্য গবেষণা: বিভিন্ন গ্রাফ পণ্যের b-ক্রোমেটিক সংখ্যা সম্পর্কে ব্যাপক গবেষণা রয়েছে, যেমন কার্টেসিয়ান পণ্য, সরাসরি পণ্য, শক্তিশালী পণ্য, অভিধান ক্রম পণ্য ইত্যাদি।

গবেষণার প্রেরণা

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

মূল অবদান

  1. মৌলিক গ্রাফ শ্রেণীর SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা সম্পূর্ণভাবে নির্ধারণ করা: পথ PnP_n, চক্র CnC_n, তারকা গ্রাফ SnS_n এবং পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফের SVN করোনার জন্য নির্ভুল b-ক্রোমেটিক সংখ্যা সূত্র প্রদান করা।
  2. সম্পূর্ণ গ্রাফ SVN করোনা গ্রাফের আংশিক ফলাফল প্রতিষ্ঠা করা: mm-ডিগ্রি n+2n+2 এর চেয়ে বেশি না হওয়া Kn⊡GK_n\boxdot G এর জন্য, এর b-ক্রোমেটিক সংখ্যা নির্ধারণ করা।
  3. নির্মাণমূলক প্রমাণ পদ্ধতি প্রদান করা: সমস্ত ফলাফল নির্দিষ্ট সর্বোত্তম b-রঙ্গ রঙ নির্মাণের মাধ্যমে প্রমাণিত হয়েছে এবং বিস্তারিত গ্রাফ উদাহরণ সহ সরবরাহ করা হয়েছে।
  4. সিস্টেমেটিক বিশ্লেষণ কাঠামো বিকাশ করা: SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা বিশ্লেষণের জন্য একটি সাধারণ পদ্ধতি এবং প্রযুক্তিগত সরঞ্জাম প্রতিষ্ঠা করা।

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

কাজের সংজ্ঞা

ইনপুট: দুটি গ্রাফ GG এবং HH, যেখানে G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}আউটপুট: SVN করোনা গ্রাফ G⊡HG\boxdot H এর b-ক্রোমেটিক সংখ্যা φ(G⊡H)\varphi(G\boxdot H)সীমাবদ্ধতা: Kn⊡GK_n\boxdot G এর ক্ষেত্রে, m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2 প্রয়োজন

SVN করোনা গ্রাফ নির্মাণ

গ্রাফ GG এবং HH দেওয়া, SVN করোনা গ্রাফ G⊡HG\boxdot H এর নির্মাণ প্রক্রিয়া:

  1. গ্রাফ GG এর সাবডিভিশন গ্রাফ S(G)S(G) থেকে শুরু করুন (প্রতিটি প্রান্তে একটি নতুন শীর্ষ সন্নিবেশ করান)
  2. ∣V(G)∣|V(G)| টি HH এর শীর্ষ-বিচ্ছিন্ন অনুলিপি যোগ করুন
  3. S(G)S(G) এর প্রতিটি মূল শীর্ষ uiu_i এর নেইবারহুডের সমস্ত শীর্ষকে (i+1)(i+1) তম HH অনুলিপির সমস্ত শীর্ষের সাথে সংযুক্ত করুন

মূল প্রযুক্তিগত সরঞ্জাম

1. m-ডিগ্রি ধারণা

nn ক্রমের গ্রাফ GG এর জন্য, এর m-ডিগ্রি সংজ্ঞায়িত করা হয়: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| যেখানে শীর্ষগুলি ডিগ্রির অ-বর্ধমান ক্রমে সাজানো হয়।

2. মৌলিক সীমাবদ্ধতা

  • নিম্ন সীমা: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (ক্রোমেটিক সংখ্যা b-ক্রোমেটিক সংখ্যা অতিক্রম করে না)
  • উচ্চ সীমা: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (b-ক্রোমেটিক সংখ্যা সর্বোচ্চ ডিগ্রি যোগ এক অতিক্রম করে না)
  • m-ডিগ্রি সীমাবদ্ধতা: φ(G)≤m(G)\varphi(G) \leq m(G)

3. SVN করোনা গ্রাফের ডিগ্রি সূত্র

G⊡HG\boxdot H এ শীর্ষ vv এর জন্য:

d_G(v), & \text{যদি } v \in V(G) \\ 2|V(H)| + 2, & \text{যদি } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{যদি } v = v_{i,j} \end{cases}$$ ### বিশ্লেষণ কৌশল পেপারটি বিভিন্ন গ্রাফ শ্রেণী সমন্বয়ের জন্য শ্রেণীবিভাগ আলোচনা পদ্ধতি ব্যবহার করে: 1. **পথের SVN করোনা গ্রাফ** (তৃতীয় অংশ) 2. **চক্রের SVN করোনা গ্রাফ** (চতুর্থ অংশ) 3. **তারকা গ্রাফের SVN করোনা গ্রাফ** (পঞ্চম অংশ) 4. **সম্পূর্ণ গ্রাফের SVN করোনা গ্রাফ** (ষষ্ঠ অংশ) প্রতিটি ক্ষেত্রে নির্দিষ্ট b-রঙ্গ রঙ নির্মাণের মাধ্যমে উচ্চ সীমার কঠোরতা প্রমাণিত হয়। ## প্রধান ফলাফল ### পথের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা **উপপাদ্য 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{যদি } n=3 \text{ এবং } t \in \{3,4\} \\ 5, & \text{যদি } (n=3 \text{ এবং } t \geq 5) \text{ বা } n \in \{4,5\} \\ n-1, & \text{যদি } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{অন্যথায়} \end{cases}$$ **উপপাদ্য 7-9**: অনুরূপভাবে $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$ এর নির্ভুল সূত্র প্রদান করা হয়েছে। ### চক্রের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা **উপপাদ্য 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{যদি } n \in \{3,4\} \\ n, & \text{যদি } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{অন্যথায়} \end{cases}$$ ### তারকা গ্রাফের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা **উপপাদ্য 17**: তারকা গ্রাফ এবং মৌলিক গ্রাফ শ্রেণীর SVN করোনা গ্রাফের জন্য, সম্পূর্ণ b-ক্রোমেটিক সংখ্যা সূত্র প্রতিষ্ঠিত হয়েছে, যেখানে মূল ফলাফল অন্তর্ভুক্ত: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### সম্পূর্ণ গ্রাফের SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা **উপপাদ্য 20-24**: m-ডিগ্রি সীমাবদ্ধতার অধীনে, $K_n\boxdot G$ এর b-ক্রোমেটিক সংখ্যা প্রদান করা হয়েছে, উদাহরণস্বরূপ: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{নির্দিষ্ট শর্তাবলী} \\ n+2, & \text{অন্যান্য শর্তাবলী} \end{cases}$$ ## প্রযুক্তিগত উদ্ভাবন বিন্দু ### 1. নির্মাণমূলক প্রমাণ পদ্ধতি - শুধুমাত্র উচ্চ সীমা প্রমাণ করা নয়, বরং স্পষ্ট নির্মাণের মাধ্যমে সর্বোত্তম b-রঙ্গ রঙ প্রমাণ করে নিম্ন সীমা প্রমাণ করা - প্রতিটি নির্মাণ বিস্তারিত গ্রাফ উদাহরণ সহ সরবরাহ করা হয়েছে, ফলাফলের যাচাইযোগ্যতা বৃদ্ধি করে ### 2. b-রংধনু সেট ধারণা b-শীর্ষ সনাক্তকরণ সহজ করার জন্য b-রংধনু সেটের ধারণা প্রবর্তন করা হয়েছে, গ্রাফে বিভিন্ন প্রতীক দিয়ে চিহ্নিত: - ক্রস ×: নির্দিষ্ট b-রংধনু সেটের শীর্ষ - ত্রিভুজ △: অন্যান্য b-শীর্ষ - বৃত্ত ●: সাধারণ শীর্ষ ### 3. মডুলার পাটিগণিত কৌশল রঙ নির্মাণে ব্যাপকভাবে মডুলার পাটিগণিত ব্যবহার করা হয় রঙের পর্যায়ক্রমিকতা এবং সঠিকতা নিশ্চিত করতে, উদাহরণস্বরূপ: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. শ্রেণীবিভাগ আলোচনার সিস্টেমেটাইজেশন প্যারামিটার পরিসীমা অনুযায়ী সূক্ষ্ম শ্রেণীবিভাগ আলোচনা, সমস্ত সম্ভাব্য ক্ষেত্র কভার নিশ্চিত করে। ## পরীক্ষামূলক যাচাইকরণ ### গ্রাফ যাচাইকরণ পেপারটি তাত্ত্বিক ফলাফল যাচাই করার জন্য অসংখ্য গ্রাফ উদাহরণ প্রদান করে: - চিত্র 2: $P_{10} \boxdot P_3$ এর সর্বোত্তম b-রঙ্গ রঙ - চিত্র 3-4: বিভিন্ন প্যারামিটারে পথের SVN করোনা গ্রাফের রঙ - চিত্র 11: চক্রের SVN করোনা গ্রাফের রঙ উদাহরণ - চিত্র 17-18: তারকা গ্রাফের SVN করোনা গ্রাফের রঙ নির্মাণ ### নির্মাণ যাচাইকরণ প্রতিটি উপপাদ্যের প্রমাণে নির্দিষ্ট রঙ নির্মাণ অ্যালগরিদম অন্তর্ভুক্ত রয়েছে, যা সরাসরি যাচাই করা যায়: 1. রঙের সঠিকতা (সংলগ্ন শীর্ষ বিভিন্ন রঙ) 2. b-শীর্ষের অস্তিত্ব (প্রতিটি রঙের একটি b-শীর্ষ রয়েছে) 3. সর্বোত্তমতা (তাত্ত্বিক সীমা অর্জন করে) ## সম্পর্কিত কাজ ### b-ক্রোমেটিক সংখ্যা গবেষণার ইতিহাস 1. **Irving-Manlove (1999)**: প্রথমবার b-ক্রোমেটিক সংখ্যা ধারণা প্রবর্তন করা 2. **বিভিন্ন গ্রাফ পণ্যের গবেষণা**: কার্টেসিয়ান পণ্য, সরাসরি পণ্য, শক্তিশালী পণ্য ইত্যাদির b-ক্রোমেটিক সংখ্যা ব্যাপকভাবে অধ্যয়ন করা হয়েছে 3. **বিশেষ গ্রাফ শ্রেণী**: পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফের b-ক্রোমেটিক সংখ্যা পরিচিত ### এই পেপারের অবস্থান - **শূন্যতা পূরণ**: SVN করোনা গ্রাফের b-ক্রোমেটিক সংখ্যা গবেষণা তুলনামূলকভাবে অপর্যাপ্ত - **পদ্ধতি উদ্ভাবন**: সিস্টেমেটিক নির্মাণ পদ্ধতি প্রদান করা - **ফলাফল সম্পূর্ণতা**: মৌলিক গ্রাফ শ্রেণী সমন্বয়ের সম্পূর্ণ ফলাফল প্রদান করা ## উপসংহার এবং আলোচনা ### প্রধান সিদ্ধান্ত 1. **সম্পূর্ণতা**: মৌলিক গ্রাফ শ্রেণী (পথ, চক্র, তারকা গ্রাফ, সম্পূর্ণ গ্রাফ) এর SVN করোনা গ্রাফের জন্য, সম্পূর্ণ b-ক্রোমেটিক সংখ্যা নির্ধারণ ফলাফল প্রদান করা হয়েছে 2. **নির্ভুলতা**: সমস্ত ফলাফল নির্ভুল মান, অনুমান বা সীমাবদ্ধতা নয় 3. **নির্মাণমূলকতা**: নির্দিষ্ট সর্বোত্তম রঙ নির্মাণ পদ্ধতি প্রদান করা হয়েছে ### সীমাবদ্ধতা 1. **গ্রাফ শ্রেণী সীমাবদ্ধতা**: শুধুমাত্র মৌলিক গ্রাফ শ্রেণী বিবেচনা করা হয়েছে, সাধারণ গ্রাফের ফলাফল আরও গবেষণার অপেক্ষায় রয়েছে 2. **সম্পূর্ণ গ্রাফ সীমাবদ্ধতা**: $K_n\boxdot G$ এর ফলাফলের জন্য m-ডিগ্রি সীমাবদ্ধতা শর্ত প্রয়োজন 3. **জটিলতা**: কিছু ক্ষেত্রে শ্রেণীবিভাগ আলোচনা অত্যন্ত জটিল ### ভবিষ্যত দিকনির্দেশনা 1. **গ্রাফ শ্রেণী সম্প্রসারণ**: আরও সাধারণ গ্রাফ শ্রেণীর SVN করোনা গ্রাফ b-ক্রোমেটিক সংখ্যা গবেষণা করা 2. **অ্যালগরিদম গবেষণা**: দক্ষ b-ক্রোমেটিক সংখ্যা গণনা অ্যালগরিদম বিকাশ করা 3. **প্রয়োগ অন্বেষণ**: ফলাফল বাস্তব নেটওয়ার্ক রঙ সমস্যায় প্রয়োগ করা ## গভীর মূল্যায়ন ### সুবিধা 1. **উল্লেখযোগ্য তাত্ত্বিক অবদান**: একটি গুরুত্বপূর্ণ গ্রাফ পণ্য শ্রেণীর b-ক্রোমেটিক সংখ্যা সমস্যা সিস্টেমেটিকভাবে সমাধান করা 2. **কঠোর পদ্ধতি**: নির্মাণমূলক প্রমাণ পদ্ধতি ফলাফলের নির্ভরযোগ্যতা নিশ্চিত করে 3. **স্পষ্ট উপস্থাপনা**: অসংখ্য গ্রাফ এবং উদাহরণ জটিল প্রমাণ বোঝা সহজ করে 4. **সম্পূর্ণ ফলাফল**: মৌলিক গ্রাফ শ্রেণীর সমস্ত গুরুত্বপূর্ণ সমন্বয় কভার করে ### অপূর্ণতা 1. **সীমিত প্রযুক্তিগত উদ্ভাবন**: প্রধানত বিদ্যমান পদ্ধতির সিস্টেমেটিক প্রয়োগ, মৌলিক নতুন প্রযুক্তির অভাব 2. **অস্পষ্ট প্রয়োগের মূল্য**: বাস্তব প্রয়োগ পরিস্থিতির আলোচনার অভাব 3. **গণনামূলক জটিলতা বিশ্লেষণ অনুপস্থিত**: নির্মাণ অ্যালগরিদমের সময় জটিলতা আলোচনা করা হয়নি ### প্রভাব 1. **তাত্ত্বিক মূল্য**: গ্রাফের b-ক্রোমেটিক সংখ্যা তত্ত্বে গুরুত্বপূর্ণ সম্পূরক প্রদান করে 2. **পদ্ধতি মূল্য**: নির্মাণ পদ্ধতি অন্যান্য গ্রাফ পণ্য গবেষণায় সাধারণীকরণ করা যায় 3. **সম্পূর্ণতা মূল্য**: SVN করোনা গ্রাফ b-ক্রোমেটিক সংখ্যা গবেষণার শূন্যতা পূরণ করে ### প্রযোজ্য পরিস্থিতি 1. **তাত্ত্বিক গবেষণা**: গ্রাফ তত্ত্ব এবং সমন্বয় অপ্টিমাইজেশন ক্ষেত্রের মৌলিক গবেষণা 2. **নেটওয়ার্ক ডিজাইন**: নেইবারহুড সীমাবদ্ধতা বিবেচনা করে এমন নেটওয়ার্ক রঙ সমস্যা 3. **অ্যালগরিদম ডিজাইন**: আরও জটিল গ্রাফ রঙ অ্যালগরিদমের মৌলিক মডিউল হিসাবে ## সংদর্ভ পেপারটি ২৫টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যার মধ্যে প্রধানগুলি অন্তর্ভুক্ত: - Irving & Manlove (1999): b-ক্রোমেটিক সংখ্যার মূল সংজ্ঞা - Kouider & Mahéo ইত্যাদি: বিভিন্ন গ্রাফ পণ্যের b-ক্রোমেটিক সংখ্যা গবেষণা - Liu & Lu (2013): SVN করোনা গ্রাফের বর্ণালী তত্ত্ব গবেষণা - Brooks (1941): গ্রাফ রঙের ক্লাসিক ফলাফল