Lévy family of graphs
گراف تھیوری میں، ریاضی کی ایک شاخ، گراف کا ایک لیوی خاندان گراف Gn، n = 1، 2، 3، کا ایک خاندان ہے، جس میں ایک خاص قسم کی "کمپیکٹنس" یا "ٹینگلڈنیس" ہوتی ہے۔ گراف کے بہت سے قدرتی طور پر پائے جانے والے خاندان لیوی خاندان ہیں۔ بہت سے ریاضی دانوں نے اس حقیقت کو نوٹ کیا ہے اور حیرت کا اظہار کیا ہے کہ ایسا لگتا ہے کہ اس کی کوئی تیار وضاحت نہیں ہے۔ رسمی طور پر، گرافوں کا ایک خاندان Gn، n = 1، 2، 3،.، ایک لیوی خاندان ہے اگر، کسی بھی جگہ کے لیے یہاں D G کا گراف قطر ہے، اور A (n) A کا n-گراف پڑوس ہے۔ نوٹ کریں کہ زیادہ سے زیادہ حد G کے ذیلی سیٹوں A پر ہوتی ہے، بشرطیکہ A کا سائز G کے نصف سے زیادہ ہو۔ الفاظ میں، اس کا مطلب یہ ہے کہ کوئی G کے کم از کم نصف سائز کا ذیلی سیٹ لے سکتا ہے، اور اسے صرف گراف کے قطر سے اڑا سکتا ہے، اور تقریبا تمام سیٹ کے ساتھ ختم ہو سکتا ہے۔ لمبا "سخت" (یعنی۔ گراف کے "کمپیکٹ" نہیں) خاندانوں جیسے کہ ترتیب n کے سائیکل گراف میں واضح طور پر ایسی خاصیت نہیں ہے: کوئی ایک ذیلی سیٹ پر غور کر سکتا ہے جو ایک نقطہ کے n/2 پڑوس پر مشتمل ہو (آدھی رات سے چھ بجے تک، جیسے)۔ گراف کا قطر D تقریبا n/2 ہے۔ لہذا ذیلی سیٹ کا-پڑوسی صرف n/2 کے سائز کا ہوتا ہے۔ ایک لیوی خاندان کے پاس یہ پڑوس ہوگا جو تقریبا تمام سیٹ کا احاطہ کرتا ہے۔ یہ واضح ہونا چاہیے کہ لیوی خاندان میں ایک بہت ہی خاص قسم کا کمپیکٹ ڈھانچہ ہونا چاہیے۔ آرڈر n کے ہائپر کیوب گراف لیوی خاندان کے طور پر جانے جاتے ہیں۔ اگر Sn وہ گراف ہے جس میں ایسے پوائنٹس ہیں جو n عناصر کے پرموٹیشن گروپ کے عناصر ہیں، جن کے کناروں میں ایسے پوائنٹس شامل ہوتے ہیں جو ٹرانسپوزیشن سے مختلف ہوتے ہیں، تو سیریز Si، i = 1,2,.، ایک لیوی خاندان ہے۔ حوالہ جات بولوباس (ایڈیٹر)۔ ممکنہ امتزاج اور اس کی ایپلی کیشنز۔ امریکن میتھمیٹیکل سوسائٹی، 1991 (p63) گراف خاندان