close

Вход

Забыли?

вход по аккаунту

?

316

код для вставкиСкачать
Degree Sequence
Conditions for Maximally
Edge-Connected Graphs and
Digraphs
Peter Dankelmann1 and Lutz Volkmann2
1
DEPARTMENT OF MATHEMATICS
AND APPLIED MATHEMATICS
UNIVERSITY OF NATAL
DURBAN, SOUTH AFRICA
E-mail: dankelma@scfs1.und.ac.za
2
LEHRSTUHL II FÜR MATHEMATIK
RWTH AACHEN
AACHEN, GERMANY
E-mail: volkm@math2.rwth-aachen.de
Received June 6, 1996
Abstract: In this paper we give simple degree sequence conditions for the equality
of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue
c 1997 John Wiley & Sons, Inc. J Graph Theory 26: 27–34, 1997
conditions for bipartite (di-)graphs. Keywords: graph, edge-connectivity, degree sequence
Sufficient conditions for the equality of the edge-connectivity and the minimum degree of a
graph were given by several authors. A classical result is the following condition for maximally
edge-connected graphs due to Chartrand [2]. Here and in the sequel a (di-)graph has no loops or
multiple edges.
c
1997 John Wiley & Sons, Inc.
CCC 0364-9024/97/010027-08
28 JOURNAL OF GRAPH THEORY
Theorem 1 [2].
If
Let G be a graph of order n with minimum degree δ and edge-connectivity λ.
δ≥
then λ = δ.
jnk
2
,
Theorem 1 was the starting point for many other sufficient conditions for λ = δ. Lesniak
[9] weakened the condition δ ≥ bn/2c to deg(u) + deg(v) ≥ n for all pairs of nonadjacent
vertices u and v in G. Plesník [10] showed that every graph of diameter 2 satisfies λ = δ and
thus generalized Lesniak's result. Improvements of Plesník's result can be found by Plesník,
Znám [11] and Dankelmann, Volkmann [3] (see also the textbook of Volkmann [11, p. 318ff]).
Goldsmith and White [8] proved that it is sufficient to have bn/2c disjoint pairs of vertices ui , vi
with deg(ui ) + deg(vi ) ≥ n. Xu gave an analogue for directed graphs, which also includes
the result by Goldsmith and White. Further conditions for λ = δ, depending on parameters not
directly related to the vertex degrees, (e.g. girth and diameter) are given in [6, 4, 5, 12].
The following degree sequence condition of Bollobás [1] includes the condition of Goldsmith
and White for odd n.
Theorem 2 [1]. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ
and edge-connectivity λ. Suppose that for every l, 1 ≤ l ≤ min{n/2 − 1, δ} we have
l
X
(di + dn−i ) ≥ ln − 1,
i=1
then λ = δ.
In this paper we give a degree sequence condition for directed graphs, which generalizes the
result by Xu, while having a much simpler proof, and implies a stronger version of Theorem 2
for undirected graphs as well.
Let D = (V, A) be a digraph with vertex set V = V (D) and arc set A = A(D). For a vertex
v ∈ V the degree of v, denoted by deg(v) is defined as the minimum value of its out-degree
deg + (v) and its in-degree deg − (v). The degree sequence of D is defined as the nonincreasing
sequence of the degrees of the vertices of D.
For two sets X, Y ⊂ V (D) we denote the set of arcs joining the vertices in X to the vertices
in Y by (X, Y ).
Theorem 3. Let D be a digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ
and arc-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and
k
X
(di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 1
i=1
for some k with 1 ≤ k ≤ δ, then λ = δ.
Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D)
with X ∪ Y = V (D) and |(X, Y )| < δ.
We first show that the sets X and Y contain at least δ +1 vertices, and therefore δ ≤ bn/2c−1.
Suppose X contains at most δ vertices. Then we obtain the contradiction
X
deg + (x) ≤ |X|(|X| − 1) + |(X, Y )| ≤ δ(|X| − 1) + |(X, Y )|.
|X|δ ≤
x∈X
DEGREE SEQUENCE CONDITIONS 29
Similarly one can show that |Y | ≥ δ + 1.
Now let S ⊂ X and T ⊂ Y be two k-sets with 1 ≤ k ≤ δ. Since every vertex in X has at
most |X| − 1 out-neighbors in X and there are at most δ − 1 arcs from X to Y , we have
X
deg + (v) ≤ k(|X| − 1) + δ − 1.
v∈S
Similarly, we have
X
deg − (v) ≤ k(|Y | − 1) + δ − 1,
v∈T
and thus, in total
X
deg(v) ≤ k(n − 2) + 2δ − 2.
(1)
v∈S∪T
Now choose S (T ) to contain the k vertices in X (Y ) of highest degree. Then S ∪ T contains
the k vertices of highest degree but not the δ + 1 − k vertices of lowest degree in D. Hence
X
deg(v) ≥
v∈S∪T
k
X
(di + dn+i−δ−1 ),
i=1
which yields together with (1) a contradiction to the hypothesis.
Theorem 3 implies the following degree sequence condition by Xu [16].
Corollary 1[16].
Let D be a digraph of order n, arc-connectivity λ and minimum degree δ. If
there are bn/2c disjoint pairs of vertices (vi , wi ) with
deg(vi ) + deg(wi ) ≥ n
for all i = 1, 2, . . . , bn/2c,
then λ = δ.
Proof. If δ ≥ bn/2c, then λ = δ by Theorem 3. If δ ≤ bn/2c − 1, then from the bn/2c
pairs of vertices choose δ pairs (v10 , w10 ), (v20 , w20 ), . . . , (vδ0 , wδ0 ) containing the δ vertices of lowest
degree of vi and wi . Then we have
δ
X
(di + dn+i−δ−1 ) ≥
i=1
δ
X
deg(vi0 ) + deg(wi0 )
i=1
≥ δn
> δ(n − 2) + 2δ − 1.
Now Theorem 3 with k = δ yields λ = δ.
Remark. The proof of Corollary 1 shows that one can relax the condition on the degrees slightly
by allowing one pair of vertices to have degree sum n − 1.
Corollary 2. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and
edge-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and
k
X
(di + dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 1
i=1
for some k with 1 ≤ k ≤ δ, then λ = δ.
30 JOURNAL OF GRAPH THEORY
Proof. Given the graph G, define the digraph D on the vertex set V (G) by replacing each
edge of G by two arcs in opposite directions and apply Theorem 3 to D.
Remark. Corollary 2 implies Theorem 1 as well as Theorem 2.
P
Remark. The following example shows that Corollary 2 is best possible in the sense that (di +
dn+i−δ−1 ) ≥ k(n − 2) + 2δ − 2 for some k ≤ δ does not guarantee λ = δ. Let H1 and H2
be two copies of the complete graph Kp with p ≥ 3, V (H1 ) = {x1 , . . . , xp }, and V (H2 ) =
{y1 , . . . , yp }. We define the graph Gp as the union of H1 and H2 together with the new edges
x1 y1 , x1 y2 , . . . , x1 yp−2 . Then n(Gp ) = n = 2p, δ(Gp ) = δ = p − 1 = n/2 − 1, λ(Gp ) = λ =
p − 2, and
δ
X
(di + dn+i−δ−1 ) = 2p(p − 1) − 2 = δ(n − 2) + 2δ − 2
i=1
In the case of a bipartite graph G, the sufficient conditions for λ = δ can be relaxed considerably. Volkmann [13], [14] proved that for a bipartite graph G instead of δ ≥ (n − 1)/2 only
δ ≥ (n + 1)/4 is needed. In contrast to non-bipartite graphs, even a neighborhood condition is
sufficient for maximally connected bipartite graphs. Dankelmann and Volkmann [3] showed that
if for every pair (u, v) of vertices of distance two |N (u) ∪ N (v)| ≥ (n + 1)/4, then λ = δ.
In the sequel let D = (V, A) denote a bipartite digraph with bipartition V = (V 0 , V 00 ). We
adopt the convention that for every subset X of V (D), we denote the set X ∩ V 0 by X 0 and
X ∩ V 00 by X 00 .
The following degree sequence condition is an analogue to Theorem 3 for bipartite digraphs.
Theorem 4. Let D be a bipartite digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥
dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or δ ≤ bn/4c and
k
X
(di + dn+1−2δ+k−i ) ≥ k(n − 2δ) + 2δ − 1
i=1
for some k with 1 ≤ k ≤ 2δ, then λ = δ.
Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D)
with X ∪ Y = V (D) and |(X, Y )| < δ.
We first show that the sets X 0 , X 00 , Y 0 and Y 00 contain at least δ vertices, and therefore
δ ≤ bn/4c.
As shown in the proof of Theorem 3, |X| ≥ δ + 1. Hence, there exists a vertex u ∈ X
with N + (u) ⊆ X. If without loss of generality u ∈ X 0 , then it follows |X 00 | ≥ δ. Now there
exists a vertex v ∈ X 00 with N + (v) ⊆ X, and hence |X 0 | ≥ δ. Similarly one can show that
|Y 0 |, |Y 00 | ≥ δ.
Now let S ⊆ X and T ⊆ Y be two k-sets with 1 ≤ k ≤ 2δ. Every vertex in X 0 has at most
|X 00 | ≤ |X| − δ out-neighbors in X. The same holds true for the vertices in X 00 . Since there are
at most δ − 1 arcs from X to Y , we have
X
deg + (v) ≤ k(|X| − δ) + δ − 1.
v∈S
Similarly, we have
X
v∈T
deg − (v) ≤ k(|Y | − δ) + δ − 1,
DEGREE SEQUENCE CONDITIONS 31
and thus, in total
X
deg(v) ≤ k(n − 2δ) + 2δ − 2.
(2)
v∈S∪T
Now choose S (T ) to contain the k vertices in X (Y ) of highest degree in D. Then S ∪ T contains
the k vertices of highest degree in G but not the 2δ − k vertices of lowest degree. Hence
X
deg(v) ≥
k
X
(di + dn+1−2δ+k−i ),
i=1
v∈S∪T
which yields, together with (2), a contradiction to the hypothesis.
As above, we obtain the following corollary for undirected bipartite graphs.
Corollary 3. Let G be a bipartite graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥
dn = δ and edge-connectivity λ. If δ ≥ b(n + 1)/4c or if δ ≤ bn/4c and
k
X
(di + dn+1−2δ+k−i ) ≥ k(n − 2δ) + 2δ − 1
i=1
for some k with 1 ≤ k ≤ 2δ, then λ = δ.
P
Remark. The following example shows that Corollary 3 is best possible in the sense that (di +
dn+1−2δ+k−i ) ≥ k(n + 2δ) + 2δ − 2 for some k ≤ 2δ does not guarantee λ = δ. Let H1 and
H2 be two copies of the complete bipartite graph Kp,p with p ≥ 1, V (H1 ) = {x01 , . . . , x0p } ∪
{x001 , . . . , x00p } and V (H2 ) = {y10 , . . . , yp0 } ∪ {y100 , . . . , yp00 }. We define the graph Gp,p as the
00
union of H1 and H2 together with the new edges x01 y100 , . . . , x0p−1 yp−1
. Then n(Gp,p ) = n =
4p, δ(Gp,p ) = δ = p = n/4, λ(Gp,p ) = λ = p − 1, and
2δ
X
(di + dn+1−i ) = 4p · 2p + 2(p − 1) = 2δ(n − 2δ) + 2δ − 2.
i=1
The following variation of Theorem 4 can be proved by choosing four sets S 0 , S 00 , T 0 , T 00 to
contain the k vertices of highest degree in X 0 , X 00 , Y 0 , Y 00 , respectively, and using estimates of
the form
X
deg + (v) ≤ k|X| + δ − 1,
v∈S 0 ∪S 00
X
deg − (v) ≤ k|Y | + δ − 1.
v∈T 0 ∪T 00
As above, the graph Gp,p shows the sharpness of the Theorem.
Theorem 5. Let D be a bipartite digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥
dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or if δ ≤ bn/4c and
k
X
i=1
di +
3k
X
i=1
for some k with 1 ≤ k ≤ δ, then λ = δ.
dn+1−δ+k−i ≥ kn + 2δ − 1
32 JOURNAL OF GRAPH THEORY
We conclude the paper with degree conditions that consider only the lower end of the degree
sequence.
Theorem 6. Let D be a digraph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ
and arc-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and
2k
X
dn+1−i ≥ kn − 3
i=1
for some k with 2 ≤ k ≤ δ, then λ = δ.
Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D)
with X ∪ Y = V (D) and |(X, Y )| < δ. As shown in Theorem 3, |X|, |Y | ≥ δ + 1 and
δ ≤ bn/2c − 1.
Now let S ⊂ X and T ⊂ Y be two k-sets with 2 ≤ k ≤ δ. If we choose S such that the
number of arcs of (X, Y ) incident with S is minimal, then we conclude
X
deg + (v) ≤ k(|X| − 1) + (δ − 1) − (δ + 1 − k) = k|X| − 2.
v∈S
Similarly, we have
X
deg − (v) ≤ k|Y | − 2,
v∈T
and thus, in total
2k
X
dn+1−i ≤
i=1
X
deg(v) ≤ kn − 4,
v∈S∪T
which yields a contradiction to the hypothesis.
Corollary 4. Let G be a graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥ dn = δ and
edge-connectivity λ. If δ ≥ bn/2c or if δ ≤ bn/2c − 1 and
2k
X
dn+1−i ≥ kn − 3
i=1
for some k with 2 ≤ k ≤ δ, then λ = δ.
Remark.
The following example shows that Corollary 4 is best possible in the sense that
P
dn+1−i ≥ kn − 4 for some k ≤ δ does not guarantee λ = δ. Let H1 and H2 be two copies
of the complete graph Kp with p ≥ 3, V (H1 ) = {x1 , . . . , xp }, and V (H2 ) = {y1 , . . . , yp }. We
define the graph Gp as the union of H1 and H2 together with the new edges x1 y1 , . . . , xp−2 yp−2 .
Then n(Gp ) = n = 2p, δ(Gp ) = δ = p − 1 = n/2 − 1, λ(Gp ) = λ = p − 2, and
2δ
X
dn+1−i = (2p − 2)p − 4 = δn − 4.
i=1
Again there is an analogue to Theorem 6 for bipartite (di)graphs.
DEGREE SEQUENCE CONDITIONS 33
Theorem 7. Let D be a bipartite (di)graph of order n with degree sequence d1 ≥ d2 ≥ · · · ≥
dn = δ and arc-connectivity λ. If δ ≥ b(n + 1)/4c or δ ≤ bn/4c and
4k
X
dn+1−i ≥ k(n + 2) − 1
i=1
for some k with 1 ≤ k ≤ δ, then λ = δ.
Proof. Suppose to the contrary that λ < δ. Then there exist two disjoint sets X, Y ⊂ V (D)
with X ∪ Y = V (D) and |(X, Y )| < δ. As shown in Theorem 4, |X 0 |, |X 00 |, |Y 0 |, |Y 00 | ≥ δ and
δ ≤ n/4.
Now let S 0 ⊆ X 0 , S 00 ⊆ X 00 , T 0 ⊆ Y 0 , and T 00 ⊆ Y 00 be four k-sets with 1 ≤ k ≤ δ, such
that the number of arcs of (X, Y ) incident with S 0 ∪ S 00 is minimal. It is easy to verify that this
number is maximal if no vertex in X is incident with more than one arc of (X, Y ) and if all the
vertices of X adjacent to vertices in Y are in the same partition set. Since X 0 and X 00 contain at
least δ vertices each, we have |(S 0 ∪ S 00 , Y )| ≤ k − 1 and thus
X
deg + (v) ≤ k|X 00 | + k|X 0 | + k − 1.
v∈S 0 ∪S 00
Similarly we have
X
deg − (v) ≤ k|Y 00 | + k|Y 0 | + k − 1.
v∈T 0 ∪T 00
and thus, in total
4k
X
i=1
dn+1−i ≤
X
deg(v) ≤ k(n + 2) − 2,
v∈S∪T
which yields a contradiction to the hypothesis.
Remark. As above, the graph Gp,p shows that
guarantee λ = δ.
P
dn+1−i ≥ k(n + 2) − 2 for some k does not
References
[1]
B. Bollobás, On graphs with equal edge-connectivity and minimum degree, Discrete Math. 28 (1979),
321–323.
[2]
G. Chartrand, A graph theoretic approach to a communications problem, SIAM J. Appl. Math. 14
(1966), 778–781.
[3]
P. Dankelmann and L. Volkmann, New sufficient conditions for equality of minimum degree and
edge-connectivity, Ars Combin. 40 (1995), 270–278.
[4]
J. Fabrega and M. A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (1989), 657–668.
[5]
J. Fabrega and M. A. Fiol, Bipartite graphs and digraphs with maximum connectivity, Discrete Appl.
Math. 69 (1996), 271–279.
[6]
M. A. Fiol, The connectivity of large digraphs and graphs, J. Graph Theory 17 (1993), 31–45.
[7]
D. L. Goldsmith and R. C. Entringer, A sufficient condition for equality of edge-connectivity and
minimum degree of a graph, J. Graph Theory. 3 (1979), 251–255.
[8]
D. L. Goldsmith and A. T. White, On graphs with equal edge-connectivity and minimum degree,
Discrete Math. 23 (1978), 31–36.
34 JOURNAL OF GRAPH THEORY
[9]
L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math. 8 (1974), 351–354.
[10]
J. Plesník, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Commenian Math. 30
(1975), 71–93.
[11]
J. Plesník and S. Znám, On equality of edge-connectivity and minimum degree of a graph, Arch. Math.
(Brno) 25 (1989), 19–25.
[12]
T. Soneoka, H. Nakada, and M. Imase, Sufficient conditions for maximally connected dense graphs,
Discrete Math. 63 (1987), 53–66.
[13]
L. Volkmann, Bemerkungen zum p-fachen Kantenzusammenhang von Graphen, An. Univ. Buccuresti
Mat. 37 (1988), 75–79.
[14]
L. Volkmann, Edge-connectivity in p-partite graphs, J. Graph Theory 13 (1989), 1–6.
[15]
L. Volkmann, Fundamente der Graphentheorie, Springer-Verlag, Wien/New York (1996).
[16]
J.-M. Xu, A sufficient condition for equality of arc-connectivity and minimum degree of a digraph,
Discrete Math. 133 (1994), 315–318.
Документ
Категория
Без категории
Просмотров
2
Размер файла
88 Кб
Теги
316
1/--страниц
Пожаловаться на содержимое документа