共查询到20条相似文献,搜索用时 140 毫秒
1.
An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least (3│G│ + 2)/2 removable edges. 相似文献
2.
Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e(G) 〉 1/2(k - 1)n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 + 37/2+ 14 and every graph G on n vertices with e(G) 〉 1/2 (k- 1)n, we prove that there exists a graph G' on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph. 相似文献
3.
LI YANG 《数学研究通讯:英文版》2014,(2):183-192
Let G be a complete p-partite graph with 2 edges removed, p ≥ 7, which is intrinsically knotted. Let J represent any graph obtained from G by a finite sequence of △-Y exchanges and/or vertex expansions. In the present paper, we show that the removal of any vertex of J and all edges incident to that vertex produces an intrinsically linked graph. This result offers more intrinsically knotted graphs which hold for the conjecture presented in Adams' book (Adams C. The Knot Book. New York: W. H. Freeman and Company, 1994), that is, the removal of any vertex from an intrinsically knotted graph yields an intrinsically linked graph. 相似文献
4.
In this paper, we prove that if any set of |E(G)|- |V(G)| + 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn't form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges. 相似文献
5.
A class of antimagic join graphs 总被引:1,自引:0,他引:1
A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic. 相似文献
6.
On 2-Factors with Prescribed Properties in a Bipartite Graph 总被引:2,自引:0,他引:2
Jin YAN Gui Zhen LIU 《数学学报(英文版)》2006,22(4):1115-1120
Liu and Yan gave the degree condition for a balanced bipartite graph G = (V1, V2; E) to have k vertex-disjoint quadrilaterals containing any given k independent edges e1,……, ek of G, respectively. They also conjectured that for any k independent edges e1,……, ek of G, G has a 2-factor with k cycles C1, C2, ……, Ck with respect to {e1, e2,……, ek} such that k - 1 of them are quadrilaterals. In this paper, we prove this conjecture. 相似文献
7.
Let G be a graph and let its maximum degree and maximum average degree be denoted byΔ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ'∑≠(G). Flandrin et al. proposed the following conjecture thatχ'∑(G) ≤Δ(G) + 2 for any connected graph with at least 3 vertices and G≠C_5. In this paper, we prove that the conjecture holds for a normal graph with mad(G) 37/12 and Δ(G) ≥ 7. 相似文献
8.
A matching is extendable in a graph G if G has a perfect matching containing it. A distance q matching is a matching such that the distance between any two distinct matching edges is at least q. In this paper, we prove that any distance 2k-3 matching is extendable in a connected and locally(k-1)-connected K1,k-free graph of even order. Furthermore, we also prove that any distance q matching M in an r-connected and locally(k-1)-connected K1,k-free graph of even or... 相似文献
9.
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n log n q- m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph. 相似文献
10.
Let G be a complete p-partite graph with 2 edges removed, p ≥ 7, which is intrinsically knotted. Let J represent any graph obtained from G by a finite sequence of ?-Y exchanges and/or vertex expansions. In the present paper, we show that the removal of any vertex of J and all edges incident to that vertex produces an intrinsically linked graph. This result offers more intrinsically knotted graphs which hold for the conjecture presented in Adams' book(Adams C. The Knot Book. New York: W. H. Freeman and Company, 1994), that is, the removal of any vertex from an intrinsically knotted graph yields an intrinsically linked graph. 相似文献
11.
(3,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7.
Revised: September 21, 1998 相似文献
12.
P. Katerinis 《Journal of Graph Theory》1987,11(1):53-58
Upper bounds are placed on the order of a k-regular m-connected graph G that produce a lower bound on the number of independent edges in G. As a corollary, we obtain the order of a smallest k-regular m-connected graph which has no 1-factor. 相似文献
13.
(2,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4].
Received: December 16, 1996 / Revised: September 17, 1997 相似文献
14.
Hong Wang 《Graphs and Combinatorics》2001,17(1):177-183
Let G=(V
1,V
2;E) be a bipartite graph with 2k≤m=|V
1|≤|V
2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
Received: December 9, 1998 Final version received: June 2, 1999 相似文献
15.
An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N
G−e
(x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present
paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4). 相似文献
16.
A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 15740077, 2005
This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists. 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
Zhi-quanHu FengTian 《应用数学学报(英文版)》2003,19(1):97-106
A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G)≥3κ-1/2 or δ(G)≥5κ-4.Several known results are generalized. 相似文献
20.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献