DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Z. Skupień

Zdzisław Skupień

Faculty of Applied MathematicsAGH University of Science and Technologyal. Mickiewicza 3030-059 KrakówPOLAND

email: skupien@agh.edu.pl

Title:

The Petersen and Heawood graphs make up graphical twins via induced matchings

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 677-683

Received: 2020-07-20 , Revised: 2021-01-26 , Accepted: 2021-01-26 , Available online: 2021-02-21 , https://doi.org/10.7151/dmgt.2394

Abstract:

Inspired by the Isaacs remark (published in 1975), we show that the Petersen and Heawood graphs ($Pg$ and $Hg$) make up a bijectively linked pair of graphs. Another related new result is that $Pg$ is uniquely decomposable into five induced 3-matchings. It shows a kind of the structural rigidity of $Pg$. Information on maximal matchings with sizes 3, 4 and 5 in $Pg$ is recalled. Constructive proofs confirm that the strong chromatic index $sq(Pg)=5$ and $sq(Hg)=7$. The three numerical edge coloring partitions for $Pg$ are also determined.

Keywords:

Heawood graph, induced matchings, Petersen graph, strong chromatic index

References:

  1. G.M. Adel'son-Vel'skiǐ and V.K. Titov, On edge $4$-chromatic cubic graphs, in: Proc. Conf. held at Moscow Univ. in Jan. 27–29, 1971, Voprosy Kibernetiki (1973) 5–14, in Russian.
  2. J.-C. Bermond, J.M.S. Simões-Pereira and C.M. Zamfirescu, On non-Hamiltonian homogeneously traceable digraphs, Math. Japon. 24 (1979/80) 423–426.
  3. G. Chartrand, R.J. Gould and S.P. Kapoor, On homogeneously traceable nonhamiltonian graphs, in: Proc. 2nd Internat. Conf. on Combinat. Math., Ann. New York Acad. Sci. 319 (1979) 130–135.
    https://doi.org/10.1111/j.1749-6632.1979.tb32783.x
  4. R.J. Faudree, R.H. Schelp, A. Gyárfás and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211.
  5. R.J. Gould, Degree sets for homogeneously traceably non-Hamiltonian graphs, Colloq. Math. 45 (1981) 155–158.
    https://doi.org/10.4064/cm-45-1-155-158
  6. P.J. Heawood, Map-colour theorem, Quart. J. Math. Oxford Ser. 24 (1890) 332–338.
  7. D.A. Holton and J. Sheehan, The Petersen Graph (Cambridge Univ. Press, Cambridge, 1993).
    https://doi.org/10.1017/CBO9780511662058
  8. R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239.
    https://doi.org/10.1080/00029890.1975.11993805
  9. J. Petersen, Sur le théorème de Tait, L'intermédiaire des Mathématiciens 5 (1898) 225–227.
  10. Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs (1976), preprint.
  11. Z. Skupień, Degrees in homogeneously traceable graphs, Ann. Discrete Math. 8 (1980) 185–188.
    https://doi.org/10.1016/S0167-5060(08)70871-9
  12. Z. Skupień, Maximum degree among vertices of a non-Hamiltonian homogeneously traceable graph, in: Combinatorics and Graph Theory, S.B. Rao (Ed(s)), Lecture Notes in Math. 885 (1981) 496–500.
  13. Z. Skupień, On homogeneously traceable nonhamiltonian digraphs and oriented graphs, in: The Theory and Applications of Graphs, G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster and D.R. Lick (Ed(s)), (Wiley, New York 1981) 517–527.
  14. Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs, Demonstr. Math. 17 (1984) 1051–1067.
    https://doi.org/10.1515/dema-1984-0424
  15. M.M. Sysło and Z. Skupień, Applied Graph Theory III Euler and Hamilton graphs. Saleman problem, Math. Appl. (Warsaw) X (1977) 5–54, in Polish.
  16. T. Zamfirescu, Three small cubic graphs with interesting Hamiltonian properties, J. Graph Theory 4 (1980) 287–292.
    https://doi.org/10.1002/jgt.3190040306
Close