共查询到20条相似文献,搜索用时 15 毫秒
1.
For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ
k
(G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U1,U2 ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U
1 and the other in U
2 by [U
1, U
2]. Define xk(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ
k
-optimal if λ
k
(G) = ξ
k
(G). A graph is said to be super-λ
k
if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ
k
-optimal or super-λ
k
. Moreover, we demonstrate that our results are best possible. 相似文献
2.
Let G = (V, E) be a connected graph. X belong to V(G) is a vertex set. X is a 3-restricted cut of G, if G- X is not connected and every component of G- X has at least three vertices. The 3-restricted connectivity κ3(G) (in short κ3) of G is the cardinality of a minimum 3-restricted cut of G. X is called κ3-cut, if |X| = κ3. A graph G is κ3-connected, if a 3-restricted cut exists. Let G be a graph girth g ≥ 4, κ3(G) is min{d(x) + d(y) + d(z) - 4 : xyz is a 2-path of G}. It will be shown that κ3(G) = ξ3(G) under the condition of girth. 相似文献
3.
Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if
G\ncong K2{G\ncong K_2}. 相似文献
4.
An edge cut of a connected graph is m-restricted if its removal leaves every component having order at least m. The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connectivity. It is known that when m≤4, networks with maximal m-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge. 相似文献
5.
Let X = (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition.
In this article, we show that every connected half vertex transitive graph X with n = |V(X)| ≥ 4 and
X \ncong K1,n-1{X \ncong K_{1,n-1}} is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also
characterized. 相似文献
6.
Qinghai Liu 《Discrete Applied Mathematics》2009,157(4):685-690
For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ3(G). A graph G is called minimally 3-restricted edge connected if λ3(G−e)<λ3(G) for each edge e∈E. A graph G is λ3-optimal if λ3(G)=ξ3(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ3-optimal except the 3-cube. 相似文献
7.
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs. 相似文献
8.
Hong‐Jian Lai 《Journal of Graph Theory》2003,42(3):211-219
Let G be a graph. For each vertex v ∈V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), Nv is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003 相似文献
9.
Ken‐ichi Kawarabayashi 《Journal of Graph Theory》2002,39(2):111-128
Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K4?‐factor (K4? is the graph obtained from K4 by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002 相似文献
10.
We analyze the structure of a continuous (or Borel) action of a connected semi-simple Lie group G with finite center and real rank at least 2 on a compact metric (or Borel) space X, using the existence of a stationary measure as the basic tool. The main result has the following corollary: Let P be a minimal parabolic subgroup of G, and K a maximal compact subgroup. Let λ be a P-invariant probability measure on X, and assume the P-action on (X,λ) is mixing. Then either λ is invariant under G, or there exists a proper parabolic subgroup Q⊂G, and a measurable G-equivariant factor map ϕ:(X,ν)→(G/Q,m), where ν=∫
K
kλdk and m is the K-invariant measure on G/Q. Furthermore, The extension has relatively G-invariant measure, namely (X,ν) is induced from a (mixing) probability measure preserving action of Q.
Oblatum 14-X-1997 & 18-XI-1998 / Published online: 20 August 1999 相似文献
11.
An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λk. In this paper, several sufficient conditions yielding super-λk graphs are given in terms of the girth and the diameter. 相似文献
12.
A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
13.
图和线图的谱性质 总被引:5,自引:0,他引:5
陈晏 《高校应用数学学报(英文版)》2002,17(3):371-376
Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite. 相似文献
14.
An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least
2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs.
Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian
(JA03147) 相似文献
15.
Some results on R
2-edge-connectivity of even regular graphs 总被引:1,自引:0,他引:1
XuJunming 《高校应用数学学报(英文版)》1999,14(3):366-370
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given. 相似文献
16.
Ying Ying TAN Yi Zheng FAN 《数学学报(英文版)》2008,24(1):139-146
Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L(G) of G. As L(G) is positive semidefinite, the singularity of L(G) is determined by its least eigenvalue λ1 (G). This paper introduces a new parameter edge singularity εs(G) that reflects the singularity of L(G), which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs(G) and λ1 (G) (and other parameters) of G. In the case of εs(G) = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 (G), which is similar to the property of Fiedler vectors of a simple graph given by Fiedler. 相似文献
17.
Donald St. P. Richards 《Annals of the Institute of Statistical Mathematics》1982,34(1):119-121
Summary LetC
κ(S) be the zonal polynomial of the symmetricm×m matrixS=(sij), corresponding to the partition κ of the non-negative integerk. If ∂/∂S is them×m matrix of differential operators with (i, j)th entry ((1+δij)∂/∂sij)/2, δ being Kronecker's delta, we show that Ck(∂/∂S)Cλ(S)=k!δλkCk(I), where λ is a partition ofk. This is used to obtain new orthogonality relations for the zonal polynomials, and to derive expressions for the coefficients
in the zonal polynomial expansion of homogenous symmetric polynomials. 相似文献
18.
It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σx∈V(H) degG(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999 相似文献
19.
Keiko Kotani 《Graphs and Combinatorics》2001,17(3):511-515
Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg
G
(x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑
x
∈
V
(
G
)
f(x) is odd.
Received: June 29, 1998?Final version received: July 30, 1999 相似文献
20.
A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs with n vertices, and let ${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$. For ${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$, we prove the sharp inequalities c(G)?[r(n?2)?2]/(2r2+2r?1)?1 and α′(G)?n/2?rb/(2r+1). Using b?[(2r?1)n+2]/(4r2+4r?2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γt(G) of a cubic graph, we prove γt(G)?n/2?b(G)/2 (except that γt(G) may be n/2?1 when b(G)=3 and the balloons cover all but one vertex). With α′(G)?n/2?b(G)/3 for cubic graphs, this improves the known inequality γt(G)?α′(G). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010 相似文献