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

Škoviera, Martin

Math. Slovaca 49, No. 2, 129-135 (1999).

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.

Reviewer: Peter Mihók (Košice)

MSC:

05C05

Trees

Keywords:

spanning tree; cotree; cycle rank; graph of diameter 2

References:

[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