1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Petersen and Heawood Graphs Make Up Graphical Twins Via Induced Matchings

Published Online: 24 Feb 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 20 Jul 2020
Accepted: 26 Jan 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

Keywords

MSC 2010

[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.Search in Google Scholar

[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.Search in Google Scholar

[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. doi:10.1111/j.1749-6632.1979.tb32783.x10.1111/j.1749-6632.1979.tb32783.xSearch in Google Scholar

[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.Search in Google Scholar

[5] R.J. Gould, Degree sets for homogeneously traceably non-Hamiltonian graphs, Colloq. Math. 45 (1981) 155–158. doi:10.4064/cm-45-1-155-15810.4064/cm-45-1-155-158Search in Google Scholar

[6] P.J. Heawood, Map-colour theorem, Quart. J. Math. Oxford Ser. 24 (1890) 332–338.Search in Google Scholar

[7] D.A. Holton and J. Sheehan, The Petersen Graph (Cambridge Univ. Press, Cambridge, 1993). doi:10.1017/CBO978051166205810.1017/CBO9780511662058Search in Google Scholar

[8] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239. doi:10.1080/00029890.1975.1199380510.1080/00029890.1975.11993805Search in Google Scholar

[9] J. Petersen, Sur le théorème de Tait, L’intermédiaire des Mathématiciens 5 (1898) 225–227.Search in Google Scholar

[10] Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs, (1976), preprint.Search in Google Scholar

[11] Z. Skupień, Degrees in homogeneously traceable graphs, Ann. Discrete Math. 8 (1980) 185–188. doi:10.1016/S0167-5060(08)70871-910.1016/S0167-5060(08)70871-9Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[14] Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs, Demonstr. Math. 17 (1984) 1051–1067. doi:10.1515/dema-1984-042410.1515/dema-1984-0424Search in Google Scholar

[15] M.M. Sys lo and Z. Skupień, Applied Graph Theory III. Euler and Hamilton graphs. Saleman problem, Math. Appl. (Warsaw) X (1977) 5–54, in Polish.10.14708/ma.v5i10.1254Search in Google Scholar

[16] T. Zamfirescu, Three small cubic graphs with interesting Hamiltonian properties, J. Graph Theory 4 (1980) 287–292. doi:10.1002/jgt.319004030610.1002/jgt.3190040306Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo