گراف شکافته

در شاخه نظریه گراف از ریاضیات، گراف شکافته (به انگلیسی: Split Graph) (یا گراف شکافته‌شده)، گرافی است که رئوس آن را می‌توان به یک کلیک و یک مجموعه مستقل افراز نمود. گراف‌های شکافته را اولین بار فولدس و همر مطالعه نموده،^[۱] و همچنین به‌طور مستقل توسط تیشکویچ و چرنیاک معرفی شدند.^[۲][۳]

ممکن است گراف شکافته شده بیش از یک افراز به کلیک و مجموعه مستقل داشته باشد؛ به عنوان مثال، مسیر a-b-c گراف شکافته شده‌ای است که رئوس آن را می‌توان به سه روش مختلف افراز نمود:

1. کلیک ${\displaystyle {a,b}}$ و مجموعه مستقل ${\displaystyle {c}}$
2. کلیک ${\displaystyle {b,c}}$ و مجموعه مستقل ${\displaystyle {a}}$
3. کلیک ${\displaystyle {b}}$ و مجموعه مستقل ${\displaystyle {a,c}}$

گراف‌های شکافته شده را می‌توان برحسب زیرگراف های القاء شده ممنوعه شان مشخصه سازی نمود: یک گراف دلخواه شکافته شده‌است اگر و تنها اگر هیچ زیرگراف القاء شده آن که چهار یا پنج رأس داشته یا دارای یک جفت یال مجزا باشد (متمم یک ۴-دور)، دوری نباشد.^[۴]

ارجاعات

1. Földes and Hammer (1977a, 1977b)
2. Tyshkevich and Chernyak (1979)
3. (Földes و Hammer 1977a) had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). (Földes و Hammer 1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is (Brandstädt، Le و Spinrad 1999), Definition 3.2.3, p.41.
4. (Földes و Hammer 1977a); (Golumbic 1980), Theorem 6.3, p. 151.

• مشارکت‌کنندگان ویکی‌پدیا. «Split Graph». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۹ مهٔ ۲۰۲۱.

منابع

• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
• Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", Information Processing Letters, 19: 37–40, doi:10.1016/0020-0190(84)90126-1.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", سالنامه ریاضیات, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ. , Baton Rouge, La. , 1977), Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Split graphs having Dilworth number two", Canadian Journal of Mathematics, 29 (3): 666–672, doi:10.4153/CJM-1977-069-1, MR 0463041.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306.
• Hammer, Peter Ladislaw; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica, 1 (3): 275–284, doi:10.1007/BF02579333, MR 0637832.
• Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", Journal of Combinatorial Theory, Series A, 73 (2): 353–359, doi:10.1016/S0097-3165(96)80012-4, MR 1370138.
• McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K_1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494, MR 0730144.
• Merris, Russell (2003), "Split graphs", European Journal of Combinatorics, 24 (4): 413–430, doi:10.1016/S0195-6698(03)00030-1, MR 1975945.
• Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
• Royle, Gordon F. (2000), "Counting set covers and split graphs" (PDF), Journal of Integer Sequences, 3 (2): 00.2.6, MR 1778996, archived from the original (PDF) on 3 March 2016, retrieved 29 May 2021.
• Tyshkevich, Regina I. (1980), "[The canonical decomposition of a graph]", Doklady Akademii Nauk SSSR (به روسی), 24: 677–679, MR 0587712
• Tyshkevich, Regina I.; Chernyak, A. A. (1979), "Canonical partition of a graph defined by the degrees of its vertices", Isv. Akad. Nauk BSSR, Ser. Fiz. -Mat. Nauk (به روسی), 5: 14–26, MR 0554162.
• Tyshkevich, Regina I.; Chernyak, A. A. (1990), Еще один метод перечисления непомеченных комбинаторных объектов, Mat. Zametki (به روسی), 48 (6): 98–105, MR 1102626. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, doi:10.1007/BF01240267.
• Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), "On graphs and degree sequences: the canonical decomposition", Kibernetika (به روسی), 6: 5–8, MR 0689420.
• Voss, H. -J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322, MR 0803929.

برای مطالعه بیشتر

• A chapter on split graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".