The maximum genus, matchings and the cycle space of a graph

Hung-Lin Fu; Martin Škoviera; Ming-Chun Tsai

Czechoslovak Mathematical Journal (1998)

  • Volume: 48, Issue: 2, page 329-339
  • ISSN: 0011-4642

Abstract

top
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ý .

How to cite

top

Fu, Hung-Lin, Škoviera, Martin, and Tsai, Ming-Chun. "The maximum genus, matchings and the cycle space of a graph." Czechoslovak Mathematical Journal 48.2 (1998): 329-339. <http://eudml.org/doc/30422>.

@article{Fu1998,
abstract = {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ý .},
author = {Fu, Hung-Lin, Škoviera, Martin, Tsai, Ming-Chun},
journal = {Czechoslovak Mathematical Journal},
keywords = {Maximum genus; matching; cycle space; maximum genus; matching; cycle space},
language = {eng},
number = {2},
pages = {329-339},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The maximum genus, matchings and the cycle space of a graph},
url = {http://eudml.org/doc/30422},
volume = {48},
year = {1998},
}

TY - JOUR
AU - Fu, Hung-Lin
AU - Škoviera, Martin
AU - Tsai, Ming-Chun
TI - The maximum genus, matchings and the cycle space of a graph
JO - Czechoslovak Mathematical Journal
PY - 1998
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 48
IS - 2
SP - 329
EP - 339
AB - 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ý .
LA - eng
KW - Maximum genus; matching; cycle space; maximum genus; matching; cycle space
UR - http://eudml.org/doc/30422
ER -

References

top
  1. Sur le couplage maximum d’un graphe, C. R. Acad. Sci. Paris (A) 247 (1958), 258–259. (1958) Zbl0086.16301MR0100850
  2. 10.1006/jctb.1994.1013, J. Combin. Theory Ser. B 60 (1994), 195–206. (1994) Zbl0794.05016MR1271269DOI10.1006/jctb.1994.1013
  3. 10.1016/1385-7258(73)90007-3, Indag. Math. 35 (1973), 228–232. (1973) MR0321809DOI10.1016/1385-7258(73)90007-3
  4. 10.1006/jctb.1993.1009, J. Combin. Theory Ser. B 57 (1993), 100–121. (1993) MR1198400DOI10.1006/jctb.1993.1009
  5. The maximum genus of planar graphs, Ukrain. Mat. Zh. 34 (1982), 97–99. (Russian) (1982) MR0647937
  6. 10.1002/jgt.3190150205, J. Graph Theory 15 (1991), 159–171. (1991) MR1106529DOI10.1002/jgt.3190150205
  7. 10.1112/jlms/s1-10.37.26, J. London Math. Soc. 10 (1935), 26–30. (1935) DOI10.1112/jlms/s1-10.37.26
  8. A characterization of upper embeddable graphs, Trans. Amer. Math. Soc. 241 (1978), 401–406. (1978) Zbl0379.05025MR0492309
  9. 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) (1980) MR0583197
  10. The maximum genus of a graph, -Transformations of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973, pp. 180–207. (Ukrainian, English summary) (1973) 
  11. ϕ -Transformations of the representation graph, Preprint 70.7, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1970. (Russian) (1970) MR0531858
  12. Graphok és matrixok, Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian) (1931) 
  13. A new characterization of the maximum genus of a graph, Czechoslovak Math. J. 31 (106) (1981), 604–613. (1981) MR0631605
  14. On 2 -cell embeddings of graphs with minimum number of regions, Czechoslovak Math. J. 35 (110) (1985), 625–631. (1985) MR0809045
  15. Characterizing the maximum genus of a connected graph, Czechoslovak Math. J. 43 (118) (1993), 177–185. (1993) MR1205240
  16. 10.1016/0095-8956(71)90036-0, J. Combin. Theory Ser. B 11 (1971), 258–267. (1971) MR0286713DOI10.1016/0095-8956(71)90036-0
  17. 10.1016/0095-8956(72)90040-8, J. Combin. Theory Ser. B 12 (1972), 260–267. (1972) MR0299523DOI10.1016/0095-8956(72)90040-8
  18. 10.1016/0095-8956(91)90099-6, J. Combin. Theory Ser. B 52 (1991), 124–146. (1991) MR1109428DOI10.1016/0095-8956(91)90099-6
  19. Graphs with 1 -factors, Proc. Amer. Math. Soc. 42 (1974), 8–12. (1974) Zbl0293.05157MR0323648
  20. The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. (1947) Zbl0029.23301MR0023048
  21. How to determine the maximum genus of a graph, J. Combin. Theory Ser. B (1979), 217–225. (1979) Zbl0403.05035MR0532589
  22. 10.1002/jgt.3190160503, J. Graph Theory 16 (1992), 399–422. (1992) Zbl0778.05033MR1185006DOI10.1002/jgt.3190160503

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.