DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 139-142
DOI: 10.7151/dmgt.1113

SOME RESULTS CONCERNING THE ENDS OF MINIMAL CUTS OF SIMPLE GRAPHS

Xiaofeng Jia

Department of Mathematics
Taiyuan University of Technology (West Campus)
Taiyuan, Shanxi, P.R. China 030024

Abstract

Let S be a cut of a simple connected graph G. If S has no proper subset that is a cut, we say S is a minimal cut of G. To a minimal cut S, a connected component of G−S is called a fragment. And a fragment with no proper subset that is a fragment is called an end. In the paper ends are characterized and it is proved that to a connected graph G = (V,E), the number of its ends Σ ≤ |V(G)|.

Keywords: cut, fragment, end, interference.

1991 Mathematics Subject Classification: 05C35, 05C40.

References

[1] B. Bollobas, Extremal Graph Theory (Academic Press, New York, 1978).
[2] H. Veldman, Non k-Critical Vertices in Graphs, Discrete Math. 44 (1983) 105-110, doi: 10.1016/0012-365X(83)90009-2.

Received 14 October 1999
Revised 24 February 2000