Lexicographic product of graphs
گراف تھیوری میں، لیکسیگرافک پروڈکٹ یا (گراف) گراف کی ساخت اور ایک ایسا گراف ہے جس کا ورٹیکس سیٹ کارٹیشین پروڈکٹ ہے۔ اور کوئی بھی دو عمودی اور اگر اور صرف اس صورت میں ملحقہ ہیں جب یا تو ان سے ملحقہ ہو یا ان سے ملحقہ ہو۔ اگر دونوں گرافوں کے کنارے کے تعلقات آرڈر کے تعلقات ہیں، تو ان کے لیکسیگرافک پروڈکٹ کا کنارے کا تعلق متعلقہ لیکسیگرافک آرڈر ہے۔ لغت کی مصنوعات کا سب سے پہلے مطالعہ کیا گیا تھا۔ جیسا کہ دکھایا گیا ہے، یہ پہچاننے کا مسئلہ کہ آیا گراف ایک لیکسیگرافک پروڈکٹ ہے، پیچیدگی میں گراف آئسومورفزم کے مسئلے کے مساوی ہے۔ خصوصیات لیکسیگرافک پروڈکٹ عام طور پر غیر متغیر ہے: تاہم یہ جداگانہ اتحاد کے حوالے سے تقسیم کے قانون کو مطمئن کرتا ہے: اس کے علاوہ یہ تکمیل کے حوالے سے ایک شناخت کو مطمئن کرتا ہے: خاص طور پر، دو خود تکمیل گرافوں کا لیکسیگرافک پروڈکٹ خود تکمیل ہے۔ لغت کی مصنوعات کی آزادی کی تعداد کا حساب آسانی سے اس کے عوامل سے لگایا جا سکتا ہے: لیکسیگرافک پروڈکٹ کا کلک نمبر بھی ضرب والا ہوتا ہے: کسی لیکسیکگرافک پروڈکٹ کا کرومیٹک نمبر G کے b-fold کرومیٹک نمبر کے برابر ہوتا ہے، کیونکہ b H کے کرومیٹک نمبر کے برابر ہوتا ہے:، جہاں۔ دو گرافوں کا لیکسیگرافک پروڈکٹ ایک کامل گراف ہے اگر اور صرف اس صورت میں جب دونوں عوامل کامل ہوں۔ حوالہ جات۔ ۔ ۔ بیرونی روابط گراف مصنوعات