共查询到20条相似文献,搜索用时 343 毫秒
1.
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}. 相似文献
2.
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. 相似文献
3.
In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?v ? V(T)max{dT(v)-k,0} £ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} . 相似文献
4.
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number
sdgt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sdgt(G) £ 2gt(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3. 相似文献
5.
6.
Jian-pingOu Fu-jiZhang 《应用数学学报(英文版)》2003,19(3):505-510
An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp. 相似文献
7.
8.
A k-dimensional box is a Cartesian product R
1 × · · · × R
k
where each R
i
is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc
graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least
p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some
a ? \mathbbN 3 2{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree
D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some
a ? \mathbbN 3 2{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with
D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if
D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some
a ? \mathbbN 3 2{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with
respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight. 相似文献
9.
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. 相似文献
10.
Zhao Zhang 《Discrete Mathematics》2008,308(20):4560-4569
An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λk(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γk(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write βk(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γk-optimal.In this paper, we first prove that λk(G)=γk(G) if G is a regular graph with girth g?k/2. Then, we show that except for K3,3 and K4, a 3-regular vertex/edge transitive graph is γk-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6ek(G)/k is γk-optimal, where ek(G) is the maximum number of edges in a subgraph of G with order k. 相似文献
11.
Xinmin Hou 《Graphs and Combinatorics》2011,27(6):865-869
Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least
?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1. 相似文献
12.
An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for
a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c¢vd(G){\chi'_{vd}(G)}. It is proved that c¢vd(G) £ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and
s2(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ
2(G) denotes the minimum degree sum of two nonadjacent vertices in G. 相似文献
13.
Martin Reiris 《Annales Henri Poincare》2010,10(8):1559-1604
Let (g, K)(k) be a CMC (vacuum) Einstein flow over a compact three-manifold Σ with non-positive Yamabe invariant (Y(Σ)). As noted by Fischer and Moncrief, the reduced volume ${\mathcal{V}(k)=\left(\frac{-k}{3}\right)^{3}{\rm Vol}_{g(k)}(\Sigma)}Let (g, K)(k) be a CMC (vacuum) Einstein flow over a compact three-manifold Σ with non-positive Yamabe invariant (Y(Σ)). As noted by Fischer and Moncrief, the reduced volume
V(k)=(\frac-k3)3Volg(k)(S){\mathcal{V}(k)=\left(\frac{-k}{3}\right)^{3}{\rm Vol}_{g(k)}(\Sigma)} is monotonically decreasing in the expanding direction and bounded below by
Vinf=(\frac-16Y(S))\frac32{\mathcal{V}_{\rm \inf}=\left(\frac{-1}{6}Y(\Sigma)\right)^{\frac{3}{2}}}. Inspired by this fact we define the ground state of the manifold Σ as “the limit” of any sequence of CMC states {(g
i
, K
i
)} satisfying: (i) k
i
= −3, (ii) Viˉ Vinf{\mathcal{V}_{i}\downarrow \mathcal{V}_{\rm inf}}, (iii) Q
0((g
i
, K
i
)) ≤ Λ, where Q
0 is the Bel–Robinson energy and Λ is any arbitrary positive constant. We prove that (as a geometric state) the ground state
is equivalent to the Thurston geometrization of Σ. Ground states classify naturally into three types. We provide examples
for each class, including a new ground state (the Double Cusp) that we analyze in detail. Finally, consider a long time and
cosmologically normalized flow
([(g)\tilde],[(K)\tilde])(s)=((\frac-k3)2g,(\frac-k3)K){(\tilde{g},\tilde{K})(\sigma)=\left(\left(\frac{-k}{3}\right)^{2}g,\left(\frac{-k}{3}\right)K\right)}, where s = -ln(-k) ? [a,¥){\sigma=-\ln (-k)\in [a,\infty)}. We prove that if [(E1)\tilde]=E1(([(g)\tilde],[(K)\tilde])) £ L{\tilde{\mathcal{E}_{1}}=\mathcal{E}_{1}((\tilde{g},\tilde{K}))\leq \Lambda} (where E1=Q0+Q1{\mathcal{E}_{1}=Q_{0}+Q_{1}}, is the sum of the zero and first order Bel–Robinson energies) the flow ([(g)\tilde],[(K)\tilde])(s){(\tilde{g},\tilde{K})(\sigma)} persistently geometrizes the three-manifold Σ and the geometrization is the ground state if Vˉ Vinf{\mathcal{V}\downarrow \mathcal{V}_{\rm inf}}. 相似文献
14.
S. El-Zanati H. Jordon G. Seelinger P. Sissokho L. Spence 《Designs, Codes and Cryptography》2010,54(2):101-107
Let n ≥ 3 be an integer, let V
n
(2) denote the vector space of dimension n over GF(2), and let c be the least residue of n modulo 3. We prove that the maximum number of 3-dimensional subspaces in V
n
(2) with pairwise intersection {0} is
\frac2n-2c7-c{\frac{2^n-2^c}{7}-c} for n ≥ 8 and c = 2. (The cases c = 0 and c = 1 have already been settled.) We then use our results to construct new optimal orthogonal arrays and (s, k, λ)-nets. 相似文献
15.
A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that
1 £ t £ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem. 相似文献
16.
17.
For a graph G of order |V(G)| = n and a real-valued mapping
f:V(G)?\mathbbR{f:V(G)\rightarrow\mathbb{R}}, if S ì V(G){S\subset V(G)} then f(S)=?w ? S f(w){f(S)=\sum_{w\in S} f(w)} is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f]=max{f(N[v])|v ? V(G)}{NS[f]={\rm max}\{f(N[v])|v \in V(G)\}} and NS(f)=max{f(N(v))|v ? V(G)}{NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}. The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, NS-[f]=min{f(N[v])|v ? V(G)}{NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}} and NS-(f)=min{f(N(v))|v ? V(G)}{NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}. For
W ì \mathbbR{W\subset \mathbb{R}}, the closed and open neighborhood sum parameters are NSW[G]=min{NS[f]|f:V(G)? W{NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W} is a bijection} and NSW(G)=min{NS(f)|f:V(G)? W{NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W} is a bijection}. The lower neighbor sum parameters are NS-W[G]=maxNS-[f]|f:V(G)? W{NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W} is a bijection} and NS-W(G)=maxNS-(f)|f:V(G)? W{NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W} is a bijection}. For bijections f:V(G)? {1,2,?,n}{f:V(G)\rightarrow \{1,2,\ldots,n\}} we consider the parameters NS[G], NS(G), NS
−[G] and NS
−(G), as well as two parameters minimizing the maximum difference in neighborhood sums. 相似文献
18.
A class Uk1 (J){\mathcal{U}}_{\kappa 1} (J) of generalized J-inner mvf’s (matrix valued functions) W(λ) which appear as resolvent matrices for bitangential interpolation problems in the generalized Schur class of p ×q mvf¢s Skp ×qp \times q \, {\rm mvf's}\, {\mathcal{S}}_{\kappa}^{p \times q} and some associated reproducing kernel Pontryagin spaces are studied. These spaces are used to describe the range of the
linear fractional transformation TW based on W and applied to Sk2p ×q{\mathcal{S}}_{\kappa 2}^{p \times q}. Factorization formulas for mvf’s W in a subclass U°k1 (J) of Uk1(J){\mathcal{U}^{\circ}_{\kappa 1}} (J)\, {\rm of}\, {\mathcal{U}}_{\kappa 1}(J) found and then used to parametrize the set Sk1+k2p ×q ?TW [ Sk2p ×q ]{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} \cap T_{W} \left[ {\mathcal{S}}_{\kappa 2}^{p \times q} \right]. Applications to bitangential interpolation problems in the class Sk1+k2p ×q{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} will be presented elsewhere. 相似文献
19.
V. V. Zhuk 《Journal of Mathematical Sciences》2010,166(2):167-185
Let L
p
, 1 ≤ p< ∞, be the space of 2π-periodic functions f with the norm
|| f ||p = ( ò - pp | f |p )1 \mathord