Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Maximum genus; matching; cycle space
Maximum genus; matching; cycle space
Summary:
In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .
References:
[1] C. Berge: Sur le couplage maximum d’un graphe. C. R. Acad. Sci. Paris (A) 247 (1958), 258–259. MR 0100850 | Zbl 0086.16301
[2] C. P. Bonnington: The relative maximum genus of a graph. J. Combin. Theory Ser. B 60 (1994), 195–206. DOI 10.1006/jctb.1994.1013 | MR 1271269 | Zbl 0794.05016
[3] G. Chartrand, A. D. Polimeni and M. J. Stewart: The existence of $1$-factors in line graphs, squares, and total graphs. Indag. Math. 35 (1973), 228–232. DOI 10.1016/1385-7258(73)90007-3 | MR 0321809
[4] J. Chen and J. Gross: Kuratowski-type theorems for average genus. J. Combin. Theory Ser. B 57 (1993), 100–121. DOI 10.1006/jctb.1993.1009 | MR 1198400
[5] A. D. Glukhov: The maximum genus of planar graphs. Ukrain. Mat. Zh. 34 (1982), 97–99. (Russian) MR 0647937
[6] J. L. Gross and R. G. Rieper: Local extrema in genus-stratified graphs. J. Graph Theory 15 (1991), 159–171. DOI 10.1002/jgt.3190150205 | MR 1106529
[7] P. Hall: On representation of subsets. J. London Math. Soc. 10 (1935), 26–30. DOI 10.1112/jlms/s1-10.37.26
[8] M. Jungerman: A characterization of upper embeddable graphs. Trans. Amer. Math. Soc. 241 (1978), 401–406. MR 0492309 | Zbl 0379.05025
[9] N. P. Khomenko and A. D. Glukhov: Single-component $2$-cell embeddings and the maximum genus of a graph. Some Topological and Combinatorial Properties of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980, pp. 5–23. (Russian) MR 0583197
[10] N. P. Khomenko, N. A. Ostroverkhy and V. A.Kuzmenko: The maximum genus of a graph. $\varphi $-Transformations of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973, pp. 180–207. (Ukrainian, English summary)
[11] N. P. Khomenko and E. V. Yavorsky: $\varphi $-Transformations of the representation graph. Preprint 70.7, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1970. (Russian) MR 0531858
[12] D. König: Graphok és matrixok. Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian)
[13] L. Nebeský: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31 (106) (1981), 604–613. MR 0631605
[14] L. Nebeský: On $2$-cell embeddings of graphs with minimum number of regions. Czechoslovak Math. J. 35 (110) (1985), 625–631. MR 0809045
[15] L. Nebeský: Characterizing the maximum genus of a connected graph. Czechoslovak Math. J. 43 (118) (1993), 177–185. MR 1205240
[16] E. A. Nordhaus, B. M. Stewart and A. T. White: On the maximum genus of a graph. J. Combin. Theory Ser. B 11 (1971), 258–267. DOI 10.1016/0095-8956(71)90036-0 | MR 0286713
[17] E. A. Nordhaus, R. D. Ringeisen, B. M. Stewart, and A. T. White: A Kuratowski-type theorem for the maximum genus of a graph. J. Combin. Theory Ser. B 12 (1972), 260–267. DOI 10.1016/0095-8956(72)90040-8 | MR 0299523
[18] J. Širáň and M. Škoviera: Characterization of the maximum genus of a signed graph. J. Combin. Theory Ser. B 52 (1991), 124–146. DOI 10.1016/0095-8956(91)90099-6 | MR 1109428
[19] D. P. Sumner: Graphs with $1$-factors. Proc. Amer. Math. Soc. 42 (1974), 8–12. MR 0323648 | Zbl 0293.05157
[20] W. T. Tutte: The factorization of linear graphs. J. London Math. Soc. 22 (1947), 107–111. MR 0023048 | Zbl 0029.23301
[21] N. H. Xuong: How to determine the maximum genus of a graph. J. Combin. Theory Ser. B (1979), 217–225. MR 0532589 | Zbl 0403.05035
[22] T. Zaslavsky: Orientation embedding of signed graphs. J. Graph Theory 16 (1992), 399–422. DOI 10.1002/jgt.3190160503 | MR 1185006 | Zbl 0778.05033
Search
Partner of
