×
Škoviera, Martin

The decay number and the maximum genus of a graph. (English) Zbl 0760.05032

Math. Slovaca 42, No. 4, 391-406 (1992).
In an earlier paper [Discrete Math. 87, No. 2, 175-180 (1991; Zbl 0724.05021)], the author calculated the maximum genus of graphs of diameter 2 and connectivity 1, and the maximum genus of loopless graphs of diameter 2. In the present paper he completes these results, by establishing the bound \(\lceil\beta(G)/2\rceil-2\leq\gamma_ M(G)\) for the maximum genus of 2-connected graphs of diameter 2 (loops and multiple edges allowed; as always, \(\gamma_ M(G)\leq\lfloor\beta(G)/2\rfloor)\). In obtaining the new lower bound, a sharp upper bound for the decay number of the connected graph \(G\) (the minimum number of components in the complement of a spanning tree) is developed, for 2-connected graphs of diameter 2.
Reviewer: A.T.White (Kalamazoo)

Cited in 1 Review
Cited in 6 Documents

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Keywords:

decay number; maximum genus; diameter 2

Citations:

Zbl 0724.05021
PDF BibTeX XML Cite
\textit{M. Škoviera}, Math. Slovaca 42, No. 4, 391--406 (1992; Zbl 0760.05032)
Full Text: EuDML

References:

[1] BOUCHET A.: Genre maximum d’un \Delta -graphe. Problèmes combinatoires et thèorie des graphes. Colloques Internat. C.N.R.S. 260, C.N.R.S., Paris, 1978, pp. 57-60. · Zbl 0413.05003
[2] CHARTRAND G., LESNIAK L.: Graphs & Digraphs, 2nd Ed. Wadsworth & Brooks-Cole, 1986. · Zbl 0666.05001
[3] JAEGER F., XUONG N. H., PAYAN C.: Genre maximal et connectivité d’un graphe. C.R. Acad. Sci. Paris Sér. A 285 (1977), 337-339. · Zbl 0369.05027
[4] KHOMENKO N. P., GLUKHOV A. D.: On upper embeddable graphs. (Russian) In: Graph Theory, Izd. Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1977, pp. 85-89. · Zbl 0433.05026
[5] KUNDU S.: Bounds on the number of disjoint spanning trees. J. Combin. Theory Ser. B 17 (1974), 199-203. · Zbl 0285.05113
[6] NEBESKÝ L.: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31(106) (1981), 604-613. · Zbl 0482.05034
[7] NEBESKÝ L.: On locally quasiconnected graphs and their upper embeddability. Czechoslovak Math. J. 35(110) (1985), 162-166. · Zbl 0584.05031
[8] ŠKOVIERA M.: The maximum genus of graphs of diameter two. Discrete Math. 87 (1991), 175-180. · Zbl 0724.05021
[9] XUONG N. H.: How to determine the maximum genus of a graph. J. Combin. Theory Ser. B 26 (1979), 217-225. · Zbl 0403.05035
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.