On the minimum number of components in a cotree of a graph. (English) Zbl 0958.05026

The decay number \(\zeta (G)\) of a simple graph \(G\) is the smallest number of components of the cotrees of \(G\), i.e., \(\zeta (G) =\min \{c (G-E(T))\): \(T\) is a spanning tree of \(G\}\), where \(c(G)\) denotes the number of components of the graph \(G\).
A leaf of graph \(G\) is any 2-edge connected subgraph of \(G\), trivial or not, maximal with respect to inclusion. The main result of the paper is the following: Let \(G\) be a connected graph and \(l(G)\) denote the number of leaves of \(G\). Then \(\zeta (G) = \max \{l(G-A) - |A|: A\subseteq E(G)\}\). An application to graphs of diameter 2 is also presented.


05C05 Trees
Full Text: EuDML


[1] BOLLOBÁS B.: Extremal Graph Theory. Academic Press, New York, 1978. · Zbl 1099.05044
[2] GLIVIAK F.: A new proof of one estimation. Istit. Lombardo Accad. Sci. Lett. Rend. A 110 (1976), 3-5. · Zbl 0368.05038
[3] MURTY U. S. R.: Extremal nonseparable graphs of diameter 2. Proof Techniques in Graph Theory, Academic Press, New York, 1969, pp. 111-118. · Zbl 0194.25403
[4] NEBESKÝ L.: Characterization of the decay number of a connected graph. Math. Slovaca 45 (1995), 349-352. · Zbl 0854.05089
[5] PALUMBÍNY D.: Sul numero minimo degli spigoli di un singramma di raggio e diametro eguali a due. Istit. Lombardo Accad. Sci. Lett. Rend. A 106 (1972), 704-712. · Zbl 0277.05133
[6] ŠIRÁŇ J.-ŠKOVIERA M.: Characterization of the maximum genus of a signed graph. J. Combin. Theory Ser. B 52 (1991), 124-146. · Zbl 0742.05037
[7] ŠKOVIERA M.: The decay number and the maximum genus of a graph. Math. Slovaca 42 (1992), 391-406. · Zbl 0760.05032
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.