Contele Harris-Wong

În teoria grafurilor, un graf Harris-Wong  este un graf nedirecționat cu 3 regulate cu 70 de vârfuri și 105 muchii [1] .

Numărul cromatic al graficului este 2, indicele cromatic este 3, diametrul și raza graficului sunt 6, iar circumferința este 10.

Graficul este un graf cubic plan hamiltonian , conectat cu 3 vârfuri, conectat cu 3 muchii .

Polinomul caracteristic al graficului Harris-Wong este

Istorie

În 1972, AT Balaban a publicat un (3-10) -cell , grafic cubic care are numărul minim de vârfuri pentru o circumferință de 10 [2] . A fost prima celulă deschisă (3-10), dar nu este unică [3] .

O listă completă de celule (3-10) și dovada minimalității au fost date de O'Keefe și Wong în 1980 [4] . Există doar trei celule distincte (3-10) - celulă Balaban cu 10 celule , graficul Harris și graficul Harris-Wong [5] . Mai mult, graficul Harris-Wong și graficul Harris sunt grafice cospectrale .

Galerie

• Numărul cromatic al contelui Harris-Wong este 2.

• Indicele cromatic al graficului Harris-Wong este 3.

• Desen alternativ al contelui Harris-Wong.

• 8 orbite ale contelui Harris - Wong.

Note

1. ^ Weisstein , Eric W. Harries–Wong Graph  pe site- ul Wolfram MathWorld .
2. ↑ Balaban, 1972 , p. 1-5.
3. ↑ Pisanski, Boben, Marusic, Orbanic, 2001 .
4. ↑ O'Keefe, Wong, 1980 , p. 91-105.
5. ↑ Bondy, Murty, 1976 , p. 237.

Literatură

• A. T. Balaban. Un grafic trivalent al fetei zece // J. Combin. Teoria Ser. B. - 1972. - Emisiune. 12 . - S. 1-5 .
• T. Pisanski, M. Boben, D. Marusic, A. Orbanic. Configurațiile Balaban generalizate // Preprint. — 2001.
• M. O'Keefe, PK Wong. Cel mai mic grafic al fetei 10 și al valenței 3 // J. Combin. Teoria Ser. B. - 1980. - Emisiune. 29 .
• JA Bondy, USR Murty. Teoria grafurilor cu aplicații . - New York: Olanda de Nord, 1976. - p  . 237 .