Bull графикасы - Bull graph - Wikipedia
| Bull графикасы | |
|---|---|
 Букалар графигі | |
| Тік | 5 |
| Шеттер | 5 |
| Радиус | 2 |
| Диаметрі | 3 |
| Гирт | 3 |
| Автоморфизмдер | 2 (З/2З) |
| Хроматикалық сан | 3 |
| Хроматикалық индекс | 3 |
| Қасиеттері | Жазықтық Бірлік арақашықтық |
| Графиктер мен параметрлер кестесі | |
Ішінде математикалық өрісі графтар теориясы, бұқа графигі Бұл жазықтық бағытталмаған граф 5 төбесі және 5 шеті бар, екі шеттік аспалы шеттері бар үшбұрыш түрінде.[1]
Онда бар хроматикалық сан 3, хроматикалық индекс 3, радиусы 2, диаметрі 3 және белдеу 3. Бұл сондай-ақ өзін-өзі толықтыратын граф, а блок-график, а бөлінген график, an аралық график, а тырнақсыз граф, 1-шыңға байланысты график және 1-шетпен байланысты график.
Өгізсіз графиктер
График бұқаларсыз, егер ол сияқты бұқалар болмаса индукцияланған субография. The үшбұрышсыз графиктер бұқаларсыз графиктер, өйткені әрбір бұқа үшбұрыштан тұрады. The күшті графикалық теорема жалпы графиктерге қарағанда бұқаларсыз графиктер үшін дәлелденген,[2] және а көпмүшелік уақыт бұқаларсыз тамаша графиканы тану алгоритмі белгілі.[3]
Мария Чудновский және Шмуэль Сафра бұқаларсыз графиктерді жалпы түрде зерттеді және кез келген осындай графиктің үлкені болуы керек екенін көрсетті клика немесе үлкен тәуелсіз жиынтық (яғни Ердис - Хажнал жорамалы бұқа графигін ұстайды),[4] және осы графиктер үшін құрылымның жалпы теориясын жасау.[5][6][7]
Хроматикалық және сипаттық көпмүшелік
The хроматикалық көпмүше бұқа графигінің . Басқа екі график хроматикалық тұрғыдан бұқа графигіне тең.
Оның тән көпмүшелік болып табылады .
Оның Тутте көпмүшесі болып табылады .
Әдебиеттер тізімі
- ^ Вайсштейн, Эрик В. «Bull Graph». MathWorld.
- ^ Чваталь, В.; Сбихи, Н. (1987), «Берге графигі - керемет», Графиктер және комбинаторика, 3 (1): 127–139, дои:10.1007 / BF01788536.
- ^ Рид, Б.; Сбихи, Н. (1995), «Бұқаларсыз мінсіз графиканы тану», Графиктер және комбинаторика, 11 (2): 171–178, дои:10.1007 / BF01929485.
- ^ Чудновский, М.; Сафра, С. (2008), «Ердис-Хаджалдың бұқаларсыз графикаға жорамалы», Комбинаторлық теория журналы, B сериясы, 98 (6): 1301–1310, дои:10.1016 / j.jctb.2008.02.005, мұрағатталған түпнұсқа 2010-06-25, алынды 2009-06-30.
- ^ Чудновский, М. (2008), Букаларсыз графиктердің құрылымы. I. Орталықтары мен антицентрлері бар үш қырлы жолдар (PDF).
- ^ Чудновский, М. (2008), Букаларсыз графиктердің құрылымы. II. Бастапқы триграфтар (PDF).
- ^ Чудновский, М. (2008), Букаларсыз графиктердің құрылымы. III. Ғаламдық құрылым (PDF).