×

Cyclic sums, network sharing, and restricted edge cuts in graphs with long cycles. (English) Zbl 1151.05029

Summary: We study graphs \(G = (V,E)\) containing a long cycle which for given integers \(a_{1}, a_{2}, \ldots , a_{k} \in \mathbb N\) have an edge cut whose removal results in \(k\) components with vertex sets \(V_{1},V_{2}, \ldots , V_{k}\) such that \(|V_{i}| \geq a_{i}\) for \(1 \leq i \leq k\). Our results closely relate to problems and recent research in network sharing and network reliability.

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Awerbuch, Fast network decomposition, Proc 11th Ann ACM Symp on principles of distributed computing pp 169– (1991)
[2] Awerbuch, Network decomposition and locality in distributed computation, Proc 30th Ann Symp on foundations of computer science pp 364– (1989)
[3] Barth, Decomposable trees: A polynomial algorithm for tripodes, Discrete Appl Math 119 pp 205– (2002) · Zbl 1002.68107
[4] Barth, A degree bound on decomposable trees, Discrete Math 306 pp 469– (2006) · Zbl 1092.05054
[5] Bezrukov, On partitioning of hypergraphs, Discrete Math 307 pp 1737– (2007) · Zbl 1129.05032
[6] Bezrukov, On bounds for the k-partitioning of graphs, Proc 5th Ann Int Conf on computing and combinatorics (COCOON 1999) pp 154– (1999) · Zbl 0949.05042
[7] Bezrukov, On partitioning grids into equal parts, Comput Artif Intell 16 pp 153– (1997) · Zbl 0871.68144
[8] Bonsma, Edge-cuts leaving components of order at least three, Discrete Math 256 pp 431– (2002) · Zbl 1017.05063
[9] Cichacz, On arbitrarily vertex decomposable unicyclic graphs with dominating cycle, Preprint Matematyka Dyskretna 020 (2006) · Zbl 1131.05071
[10] Esfahanian, Generalized measures of fault tolerance with application to N-cube networks, IEEE Trans Comput 38 pp 1586– (1989)
[11] Esfahanian, On computing a conditional edge-connectivity of a graph, Inform Process Lett 27 pp 195– (1988) · Zbl 0633.05045
[12] Györi, On division of graphs to connected subgraphs, Combinatorics (Proc. 5th Hungarian Colloq, Keszthely, 1976) pp 485– (1978) · Zbl 0388.05008
[13] Harary, Conditional connectivity, Networks 13 pp 347– (1983)
[14] Hellwig, Cuts leaving components of given minimal order, Discrete Math 292 pp 55– (2005) · Zbl 1063.05079
[15] Horňák, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opusc Math 23 pp 49– (2003) · Zbl 1093.05510
[16] Kalinowski, Arbitrarily vertex decomposable suns with few rays, Preprint Matematyka Dyskretna 015 (2006) · Zbl 1214.05125
[17] Linial, Decomposing graphs into regions of small diameter, Proc 2nd Ann ACM-SIAM Symp on discrete algorithms pp 320– (1991) · Zbl 0785.05073
[18] Lovász, A homology theory for spanning trees of a graph, Acta Math Acad Sci Hungar 30 pp 241– (1977)
[19] Marczyk, A note on arbitrarily vertex decomposable graphs, Opusc Math 26 pp 109– (2006) · Zbl 1134.05083
[20] Ou, Edge cuts leaving components of order at least m, Discrete Math 305 pp 365– (2005) · Zbl 1078.05052
[21] Wang, Conditional edge connectivity properties, reliability comparisons and transitivity of graphs, Discrete Math 258 pp 205– (2002) · Zbl 1012.05101
[22] Zhang, A proof of an inequality concerning k-restricted edge connectivity, Discrete Math 304 pp 128– (2005) · Zbl 1081.05060
[23] Zhang, Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal, Discrete Math 307 pp 293– (2007) · Zbl 1177.05067
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.