Mikelskiy - Mycielskian

In matematik maydoni grafik nazariyasi, Mikelskiy yoki Mitsel grafigi ning yo'naltirilmagan grafik undan tuzilishi natijasida hosil bo'lgan kattaroq grafik Yan Mitselskiy  (1955 ). Qurilish mavjudlik xususiyatini saqlaydi uchburchaksiz lekin oshiradi xromatik raqam; uchburchaksiz boshlang'ich grafigiga konstruktsiyani qayta-qayta qo'llash orqali Mitselskiy o'zboshimchalik bilan katta xromatik songa ega uchburchaksiz grafikalar mavjudligini ko'rsatdi.

Qurilish

Mitsel qurilishi 5- ga nisbatan qo'llanilgantsikl grafigi ishlab chiqarish Grotzsh grafigi 11 ta tepalik va 20 ta qirrali, eng kichik uchburchaksiz 4-xromatik grafika (Chvatal 1974 yil ).

Ruxsat bering n berilgan grafaning tepalari G bo'lishi v₁, v₂, . . . , v_n. Mitsel grafigi m (G) o'z ichiga oladi G o'zi bilan birga subgraf sifatida n+1 qo'shimcha tepaliklar: tepalik siz_men har bir tepaga to'g'ri keladi v_men ning Gva qo'shimcha vertex w. Har bir tepalik siz_men ga chekka bilan bog'langan w, shuning uchun bu tepaliklar yulduz shaklida subgraf hosil qiladi K_1,n. Bundan tashqari, har bir chekka uchun v_menv_j ning G, Mitsel grafigi ikkita qirrani o'z ichiga oladi, siz_menv_j va v_mensiz_j.

Shunday qilib, agar G bor n tepaliklar va m qirralar, m (G) 2 ga egan+1 tepaliklar va 3m+n qirralar.

M dagi yangi uchburchaklar (G) shaklga ega v_menv_jsiz_k, qayerda v_menv_jv_k ning uchburchagi G. Shunday qilib, agar G uchburchaksiz, m (G).

Qurilish xromatik sonni ko'paytirayotganini ko'rish uchun ${displaystyle chi (G) = k}$, to'g'ri deb hisoblang k- rang berish ${displaystyle mu (G) {-} {w}}$; ya'ni xaritalash ${displaystyle c: {v_ {1}, ldots, v_ {n}, u_ {1}, ldots, u_ {n}} o {1,2, ldots, k}}$ bilan ${displaystyle c (x) eq c (y)}$ qo'shni tepaliklar uchun x,y. Agar bizda bo'lsa ${displaystyle c (u_ {i}) kichik to'plam {1,2, ldots, k {-} 1}}$ Barcha uchun men, keyin biz to'g'ri (k−1) - rang berish G tomonidan ${displaystyle c '! (v_ {i}) = c (u_ {i})}$ qachon ${displaystyle c (v_ {i}) = k}$va ${displaystyle c '! (v_ {i}) = c (v_ {i})}$ aks holda. Ammo buning iloji yo'q ${displaystyle chi (G) = k}$, shuning uchun v barchasini ishlatishi kerak k uchun ranglar ${displaystyle {u_ {1}, ldots, u_ {n}}}$va oxirgi tepalikning har qanday to'g'ri ranglanishi w qo'shimcha rangdan foydalanish kerak. Anavi, ${displaystyle chi (mu (G)) = k {+} 1}$.

Mitselliklar takrorlandi

M₂, M₃ va M₄ Mitsel grafikalari

Mycielskiani bir qirrali grafigidan boshlab qayta-qayta qo'llash grafika ketma-ketligini hosil qiladi M_men = m (M_men−1), ba'zan Mitsel grafiklari deb nomlanadi. Ushbu ketma-ketlikdagi dastlabki bir nechta grafikalar grafikalardir M₂ = K₂ chekka bilan bog'langan ikkita tepalik bilan tsikl grafigi M₃ = C₅, va Grotzsh grafigi M₄ 11 ta tepalik va 20 ta chekka bilan.

Umuman olganda, grafik M_men bu uchburchaksiz, (men−1)-tepaga ulangan va men-xromatik. Tepaliklar soni M_men uchun men ≥ 2 - 3 × 2^men−2 - 1 (ketma-ketlik) A083329 ichida OEIS ), qirralarning soni esa men = 2, 3,. . . bu:

1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (ketma-ketlik A122695 ichida OEIS ).

Xususiyatlari

Hamilton tsikli M₄ (Grotzsh grafigi)

• Agar G bor xromatik raqam k, keyin m (G) xromatik raqamga ega k + 1 (Mitselskiy 1955 yil ).
• Agar G bu uchburchaksiz, keyin m (G) (Mitselskiy 1955 yil ).
• Umuman olganda, agar G bor klik raqami ω (G), keyin m (G) maksimal (2, ω (G)).(Mitselskiy 1955 yil ).
• Agar G a omil-muhim grafik, keyin m (G) (Došlić 2005 yil ). Xususan, har bir grafik M_men uchun men ≥ 2 omil uchun juda muhimdir.
• Agar G bor Gamilton tsikli, keyin m (G) (Fisher, McKenna & Boyer 1998 yil ).
• Agar G bor hukmronlik raqami γ (G), keyin m (G) dominantlik raqami γ (G)+1. (Fisher, McKenna & Boyer 1998 yil ).

Grafalar ustidagi konuslar

5 tsiklda konus shaklida hosil bo'lgan umumiy miksiyan, Δ₃(C₅) = Δ₃(Δ₂(K₂)).

Mycielskianing grafada konus deb nomlangan umumlashtirilishi tomonidan kiritilgan Stiebitz (1985) va keyinchalik o'rganilgan Tardif (2001) va Lin va boshq. (2006). Ushbu qurilishda bittasi g grafikasini hosil qiladi_men(G) berilgan grafikadan G olib grafiklarning tensor mahsuloti G × H, qayerda H uzunlik yo'lidir men bir uchida o'z-o'zidan halqa bilan, so'ngra bitta supervertexga aylanib, tepalik bilan bog'liq barcha tepaliklar H yo'lning pastadir qismida. Mitselning o'zi shu tarzda m (G) = Δ₂(G).

Konusning konstruktsiyasi har doim ham kromatik sonni ko'paytirmasa ham, Stiebitz (1985) ga takroriy qo'llanilganda buni amalga oshirishini isbotladi K₂. Ya'ni, umumiy miksiyaliklar deb nomlangan grafikalar oilalarining ketma-ketligini aniqlang

B (2) = {K₂} va ℳ (k+1) = {Δ_men(G) | G ℳ (k), i ∈ ℕ}.

Masalan, d (3) - toq sikllar oilasi. Keyin har bir grafika ℳ (k) k-xromatik. Isbotida usullaridan foydalaniladi topologik kombinatorika tomonidan ishlab chiqilgan Laslo Lovásh ning xromatik sonini hisoblash uchun Kneser grafikalari.Uchburchaksiz xususiyat quyidagi tarzda mustahkamlanadi: agar bitta konus konstruktsiyasini applies ishlatsa_men uchun men ≥ r, keyin olingan grafaga ega g'alati to'shak kamida 2r + 1, ya'ni unda 2 dan kichik uzunlikdagi toq tsikllar bo'lmaydir + 1. Shunday qilib, Mitseliyaliklar umumlashtirilib, yuqori xromatik son va g'alati to'shakka ega bo'lgan grafiklarning sodda tuzilishini ta'minlaydi.

Adabiyotlar

• Chvatal, Vashek (1974), "Mitsel grafigining minimalligi", Grafika va kombinatorika (Proc. Capital Conf., George Vashington universiteti, Vashington, D.C., 1973), Matematikadan ma'ruza matnlari, 406, Springer-Verlag, 243-246 betlar.
• Doshlić, Tomislav (2005), "Mitselliklar va o'yinlar", Mathematicae grafik nazariyasini muhokama qiladi, 25 (3): 261–266, doi:10.7151 / dmgt.1279, JANOB  2232992.
• Fisher, Devid S.; McKenna, Patricia A.; Boyer, Yelizaveta D. (1998), "Mikilskiy grafikalarining hamiltonikligi, diametri, ustunligi, qadoqlanishi va ikki qismli bo'linmalari", Diskret amaliy matematika, 84 (1–3): 93–105, doi:10.1016 / S0166-218X (97) 00126-1.
• Lin, Vensong; Vu, Tszianzuan; Lam, Piter Che Bor; Gu, Guohua (2006), "Umumiy miksiyaliklarning bir nechta parametrlari", Diskret amaliy matematika, 154 (8): 1173–1182, doi:10.1016 / j.dam.2005.11.001.
• Mitsel, Yanvar (1955), "Sur le coloriage des graphes" (PDF), Kolloq. Matematika., 3: 161–162.
• Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Habilitatsiya tezisi, Technische Universität Ilmenau. Iqtibos sifatida Tardif (2001).
• Tardif, C. (2001), "Grafalar ustida konusning fraksiyonel kromatik raqamlari", Grafika nazariyasi jurnali, 38 (2): 87–94, doi:10.1002 / jgt.1025.

Tashqi havolalar

• Vayshteyn, Erik V. "Mycielski Graph". MathWorld.