| Title:
|
The maximum genus, matchings and the cycle space of a graph (English) |
| Author:
|
Fu, Hung-Lin |
| Author:
|
Škoviera, Martin |
| Author:
|
Tsai, Ming-Chun |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
48 |
| Issue:
|
2 |
| Year:
|
1998 |
| Pages:
|
329-339 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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ý . (English) |
| Keyword:
|
Maximum genus |
| Keyword:
|
matching |
| Keyword:
|
cycle space |
| MSC:
|
05C10 |
| MSC:
|
05C38 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 0949.05015 |
| idMR:
|
MR1624256 |
| . |
| Date available:
|
2009-09-24T10:13:54Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127420 |
| . |
| Reference:
|
[1] C. Berge: Sur le couplage maximum d’un graphe.C. R. Acad. Sci. Paris (A) 247 (1958), 258–259. Zbl 0086.16301, MR 0100850 |
| Reference:
|
[2] C. P. Bonnington: The relative maximum genus of a graph.J. Combin. Theory Ser. B 60 (1994), 195–206. Zbl 0794.05016, MR 1271269, 10.1006/jctb.1994.1013 |
| Reference:
|
[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. MR 0321809, 10.1016/1385-7258(73)90007-3 |
| Reference:
|
[4] J. Chen and J. Gross: Kuratowski-type theorems for average genus.J. Combin. Theory Ser. B 57 (1993), 100–121. MR 1198400, 10.1006/jctb.1993.1009 |
| Reference:
|
[5] A. D. Glukhov: The maximum genus of planar graphs.Ukrain. Mat. Zh. 34 (1982), 97–99. (Russian) MR 0647937 |
| Reference:
|
[6] J. L. Gross and R. G. Rieper: Local extrema in genus-stratified graphs.J. Graph Theory 15 (1991), 159–171. MR 1106529, 10.1002/jgt.3190150205 |
| Reference:
|
[7] P. Hall: On representation of subsets.J. London Math. Soc. 10 (1935), 26–30. 10.1112/jlms/s1-10.37.26 |
| Reference:
|
[8] M. Jungerman: A characterization of upper embeddable graphs.Trans. Amer. Math. Soc. 241 (1978), 401–406. Zbl 0379.05025, MR 0492309 |
| Reference:
|
[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 |
| Reference:
|
[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) |
| Reference:
|
[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 |
| Reference:
|
[12] D. König: Graphok és matrixok.Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian) |
| Reference:
|
[13] L. Nebeský: A new characterization of the maximum genus of a graph.Czechoslovak Math. J. 31 (106) (1981), 604–613. MR 0631605 |
| Reference:
|
[14] L. Nebeský: On $2$-cell embeddings of graphs with minimum number of regions.Czechoslovak Math. J. 35 (110) (1985), 625–631. MR 0809045 |
| Reference:
|
[15] L. Nebeský: Characterizing the maximum genus of a connected graph.Czechoslovak Math. J. 43 (118) (1993), 177–185. MR 1205240 |
| Reference:
|
[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. MR 0286713, 10.1016/0095-8956(71)90036-0 |
| Reference:
|
[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. MR 0299523, 10.1016/0095-8956(72)90040-8 |
| Reference:
|
[18] J. Širáň and M. Škoviera: Characterization of the maximum genus of a signed graph.J. Combin. Theory Ser. B 52 (1991), 124–146. MR 1109428, 10.1016/0095-8956(91)90099-6 |
| Reference:
|
[19] D. P. Sumner: Graphs with $1$-factors.Proc. Amer. Math. Soc. 42 (1974), 8–12. Zbl 0293.05157, MR 0323648 |
| Reference:
|
[20] W. T. Tutte: The factorization of linear graphs.J. London Math. Soc. 22 (1947), 107–111. Zbl 0029.23301, MR 0023048 |
| Reference:
|
[21] N. H. Xuong: How to determine the maximum genus of a graph.J. Combin. Theory Ser. B (1979), 217–225. Zbl 0403.05035, MR 0532589 |
| Reference:
|
[22] T. Zaslavsky: Orientation embedding of signed graphs.J. Graph Theory 16 (1992), 399–422. Zbl 0778.05033, MR 1185006, 10.1002/jgt.3190160503 |
| . |
