Name
Abstract | ||
|---|---|---|
It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev
1, ...,v
n
≠V(G) and for any sequence of positive integersk
1, ...,k
n
such thatk
1+...+k
n
=|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv
1, ...,v(n), and the class of the partition containingv
i
induces a connected subgraph consisting ofk
i
vertices, fori=1, 2, ...,n. Now fix the integersk
1, ...,k
n
. In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv
1, ...,v
n
≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG. |
Year | DOI | Venue |
|---|---|---|
1981 | 10.1007/BF02579332 | Combinatorica |
Keywords | Field | DocType |
connected graph,lower bound | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Vertex connectivity,Frequency partition of a graph,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
1 | 3 | 1439-6912 |
Citations | PageRank | References |
1 | 0.36 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ervin Györi | 1 | 88 | 21.62 |