Tietze's graph
গ্রাফ তত্ত্বের গাণিতিক ক্ষেত্রে, টিটজের গ্রাফটি 12টি শীর্ষ এবং 18টি প্রান্ত সহ একটি অনির্দিষ্ট ঘন গ্রাফ। এটি হাইনরিখ ফ্রাঞ্জ ফ্রেডরিখ টিটজের নামে নামকরণ করা হয়েছে, যিনি 1910 সালে দেখিয়েছিলেন যে মোবিয়াস স্ট্রিপকে ছয়টি অঞ্চলে বিভক্ত করা যেতে পারে যা একে অপরকে স্পর্শ করে-তিনটি স্ট্রিপের সীমানা বরাবর এবং তিনটি তার কেন্দ্র রেখা বরাবর-এবং তাই মোবিয়াস স্ট্রিপের উপর এম্বেড করা গ্রাফগুলির জন্য ছয়টি রঙের প্রয়োজন হতে পারে। তিয়েৎজের মহকুমার অঞ্চলগুলির সীমানা বিভাগগুলি (মোবিয়াস স্ট্রিপের সীমানা বরাবর বিভাগগুলি সহ) তিয়েৎজের গ্রাফের একটি এম্বেডিং গঠন করে। পিটারসেনের গ্রাফের সঙ্গে টিটজের গ্রাফের সম্পর্ক পিটারসেনের গ্রাফ থেকে একটি শীর্ষকে ত্রিভুজ দিয়ে প্রতিস্থাপন করে তৈরি করা যেতে পারে। টিটজে গ্রাফের মতো, পিটারসেন গ্রাফ ছয়টি পারস্পরিক স্পর্শকারী অঞ্চলের সীমানা গঠন করে, তবে মোবিয়াস স্ট্রিপের পরিবর্তে প্রজেক্টিভ সমতলে। যদি কেউ প্রজেক্টিভ সমতলের এই উপবিভাগ থেকে একটি একক শীর্ষকে ঘিরে একটি গর্ত কেটে ফেলে, তবে বেষ্টিত শীর্ষটি গর্তের চারপাশে অঞ্চলের সীমানার একটি ত্রিভুজ দ্বারা প্রতিস্থাপিত হয়, যা পূর্বে বর্ণিত টিটজে গ্রাফের গঠন দেয়। হ্যামিল্টনিসিটি টিটজের গ্রাফ এবং পিটারসেনের গ্রাফ উভয়ই সর্বাধিক অ-হ্যামিল্টনীয়ঃ তাদের কোনও হ্যামিল্টনীয় চক্র নেই, তবে যে কোনও দুটি অ-সংলগ্ন শীর্ষকে হ্যামিল্টনীয় পথ দ্বারা সংযুক্ত করা যেতে পারে। টিটজের গ্রাফ এবং পিটারসেনের গ্রাফ হল একমাত্র 2-ভার্টেক্স-সংযুক্ত ঘন অ-হ্যামিল্টনিয়ান গ্রাফ যার 12 বা তার কম শীর্ষ রয়েছে। পিটারসেন গ্রাফের বিপরীতে, টিটজের গ্রাফটি হাইপোহ্যামিল্টোনিয়ান নয়ঃ এর তিনটি ত্রিভুজ শীর্ষের মধ্যে একটি অপসারণ একটি ছোট গ্রাফ গঠন করে যা অ-হ্যামিল্টোনিয়ান থাকে। প্রান্তের রঙ এবং নিখুঁত ম্যাচিং প্রান্তের রঙ করার জন্য টিটজের গ্রাফের চারটি রঙের প্রয়োজন; অর্থাৎ, এর ক্রোমাটিক সূচক হল 4। সমতুল্যভাবে, টিটজের গ্রাফের প্রান্তগুলি চারটি ম্যাচে বিভক্ত করা যেতে পারে, তবে কম নয়। টিটজের গ্রাফ একটি স্নার্কের সংজ্ঞার অংশের সাথে মেলেঃ এটি একটি ঘন সেতুহীন গ্রাফ যা 3-প্রান্ত-রঙিন নয়। যাইহোক, বেশিরভাগ লেখক 3-চক্র ছাড়া গ্রাফগুলিতে স্নার্ক সীমাবদ্ধ করেন, তাই টিটজের গ্রাফকে সাধারণত স্নার্ক হিসাবে বিবেচনা করা হয় না। তা সত্ত্বেও, এটি জে3 গ্রাফের সমতুল্য, যা 1975 সালে আর. আইজাকস দ্বারা প্রবর্তিত ফুলের স্নার্কের একটি অসীম পরিবারের অংশ। পিটারসেন গ্রাফের বিপরীতে, টিটজে গ্রাফটি চারটি নিখুঁত মিল দ্বারা আচ্ছাদিত করা যেতে পারে। এই বৈশিষ্ট্যটি একটি প্রমাণের ক্ষেত্রে মূল ভূমিকা পালন করে যে একটি গ্রাফ চারটি নিখুঁত মিল দ্বারা আচ্ছাদিত করা যেতে পারে কিনা তা পরীক্ষা করা এনপি-সম্পূর্ণ। অতিরিক্ত বৈশিষ্ট্য টিৎজের গ্রাফের ক্রোমাটিক সংখ্যা 3, ক্রোমাটিক সূচক 4, ঘের 3 এবং ব্যাস 3 রয়েছে। স্বাধীনতা সংখ্যা হল 5। এর অটোমরফিজম গ্রুপের ক্রম 12 রয়েছে এবং এটি ডাইহেড্রাল গ্রুপ ডি 6-এর সমতুল্য, যা একটি ষড়ভুজ সমমিতির গ্রুপ, যার মধ্যে ঘূর্ণন এবং প্রতিফলন উভয়ই রয়েছে। এই গোষ্ঠীর শীর্ষে 3 আকারের দুটি কক্ষপথ এবং 6 আকারের একটি কক্ষপথ রয়েছে এবং তাই এই গ্রাফটি ভার্টেক্স-ট্রানজিটিভ নয়। গ্যালারি আরও দেখুন ড্যুরার গ্রাফ এবং ফ্রাঙ্কলিন গ্রাফ, আরও দুটি 12-ভার্টেক্স কিউবিক গ্রাফ নোটস স্বতন্ত্র গ্রাফ নিয়মিত গ্রাফ