The maximum genus of a 3-regular simplicial graph. (English) Zbl 0945.05017
Authors’ abstract: The relationship between the non-separating independent number and the maximum genus of a 3-regular simplicial graph is presented. A lower bound on the maximum genus of a 3-regular graph involving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.
Reviewer: G.Chaty (Paris)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Chen, J., Archdeacon, D. and Gross, J.L., Maximum genus and connectivity, Discrete Math., 1996, 149:19–29. · Zbl 0843.05019 · doi:10.1016/0012-365X(94)00336-H |
| [2] | Chen, J., Kanchi, S.P. and Gross, J.L., A tight lower bound on maximum genus of a simplicial graph, Discrete Math., 1996, 156:83–102. · Zbl 0858.05041 · doi:10.1016/0012-365X(95)00070-D |
| [3] | Kundu, S., Bounds on number of disjoint spanning trees, J. Combin. Theory Ser. B, 1974, 17:199–203. · Zbl 0285.05113 · doi:10.1016/0095-8956(74)90087-2 |
| [4] | Liu, Y., Embeddability in Graphs, Kluwer & Science, Dordrecht, 1995. · Zbl 0863.05027 |
| [5] | Speckenmeyer, E., On the feedback vertex set and nonseparating independent sets in cubic graphs, J. Graph Theory, 1988, 12:405–412. · Zbl 0657.05042 · doi:10.1002/jgt.3190120311 |
| [6] | Xuong, N.H., How to determine the maximum genus of a graph, J. Combin. Theory Ser. B, 1979, 26:217–224. · Zbl 0403.05035 · doi:10.1016/0095-8956(79)90058-3 |
| [7] | Jungerman, M., A characterization of upper embeddable graphs, Trans. Amer. Math. Soc., 1978, 241:401–406. · Zbl 0379.05025 |
| [8] | Huang, Y. and Liu, Y., Maximum genus and maximum nonseparating independent set of a 3-regular graph, Discrete Math., 1997, 176:149–158. · Zbl 0888.05020 · doi:10.1016/S0012-365X(96)00299-3 |
| [9] | Staton, W., Induced forests in cubic graphs, Discrete Math., 1984, 49:175–178. · Zbl 0536.05015 · doi:10.1016/0012-365X(84)90115-8 |
| [10] | Bondy, J.A., Hopkins, G. and Staton, W., Lower bounds for induced forests in cubic graphs, Canad. Math. Bull., 1987, 30:193–199. · Zbl 0582.05020 · doi:10.4153/CMB-1987-028-5 |
| [11] | Xuong, N.H., Upper embeddable graphs and related topics, J. Combin. Theory Ser. B, 1979, 26: 225–232. · Zbl 0403.05036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
