Lexicographic product of graphs
গ্রাফ তত্ত্বে, লেক্সিকোগ্রাফিক পণ্য বা (গ্রাফ) গ্রাফের গঠন এবং এটি এমন একটি গ্রাফ যাতে এর শীর্ষ সেটটি কার্টেসিয়ান পণ্য হয়; এবং যে কোনও দুটি শীর্ষ এবং যদি এবং কেবল তখনই সংলগ্ন হয় যদি উভয়ই ভিতরে বা সংলগ্ন থাকে এবং সংলগ্ন থাকে। যদি দুটি গ্রাফের প্রান্ত সম্পর্কগুলি ক্রম সম্পর্ক হয়, তবে তাদের অভিধানগত পণ্যের প্রান্ত সম্পর্কটি সংশ্লিষ্ট অভিধানগত ক্রম। লেক্সিকোগ্রাফিক পণ্যটি প্রথম অধ্যয়ন করেছিলেন। যেমন দেখানো হয়েছে, একটি গ্রাফ একটি অভিধানগত পণ্য কিনা তা শনাক্ত করার সমস্যাটি জটিলতায় গ্রাফের সমরূপতা সমস্যার সমতুল্য। বৈশিষ্ট্য অভিধান সংক্রান্ত পণ্যটি সাধারণভাবে অ-বিনিময়যোগ্যঃ তবে এটি বিচ্ছিন্ন ইউনিয়নের ক্ষেত্রে একটি বিতরণমূলক আইনকে সন্তুষ্ট করেঃ উপরন্তু এটি পরিপূরকের ক্ষেত্রে একটি পরিচয়কে সন্তুষ্ট করেঃ বিশেষ করে, দুটি স্ব-পরিপূরক গ্রাফের অভিধানগত পণ্য স্ব-পরিপূরক। একটি অভিধানগত পণ্যের স্বাধীন সংখ্যা সহজেই তার কারণগুলি থেকে গণনা করা যেতে পারেঃ একটি অভিধান সংক্রান্ত পণ্যের চক্র সংখ্যাও গুণনীয়কঃ একটি অভিধানগত পণ্যের ক্রোমাটিক সংখ্যা জি-এর বি-গুণিত ক্রোমাটিক সংখ্যার সমান, যেখানে বি-এর জন্য এইচ-এর ক্রোমাটিক সংখ্যার সমান। দুটি গ্রাফের অভিধানগত পণ্য একটি নিখুঁত গ্রাফ হয় যদি এবং শুধুমাত্র যদি উভয় কারণই নিখুঁত হয়। রেফারেন্স। । । বাহ্যিক লিঙ্ক গ্রাফ পণ্য