共查询到20条相似文献,搜索用时 531 毫秒
1.
Ken-ichi Kawarabayashi Orlando Lee Bruce Reed Paul Wollan 《Journal of Combinatorial Theory, Series B》2008,98(5):972-979
We prove there exists a function f(k) such that for every f(k)-connected graph G and for every edge eE(G), there exists an induced cycle C containing e such that G−E(C) is k-connected. This proves a weakening of a conjecture of Lovász due to Kriesell. 相似文献
2.
On shredders and vertex connectivity augmentation 总被引:1,自引:0,他引:1
We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight. 相似文献
3.
Let G be a graph. For u,vV(G) with distG(u,v)=2, denote JG(u,v)={wNG(u)∩NG(v)|NG(w)NG(u)NG(v){u,v}}. A graph G is called quasi claw-free if JG(u,v)≠ for any u,vV(G) with distG(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected. 相似文献
4.
Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑e′N[e]f(e′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs Gm,k with . 相似文献
5.
Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp. 相似文献
6.
We investigate the following modification of the well-known irregularity strength of graphs. Given a total weighting w of a graph G=(V,E) with elements of a set {1,2,…,s}, denote wtG(v)=∑evw(e)+w(v) for each vV. The smallest s for which exists such a weighting with wtG(u)≠wtG(v) whenever u and v are distinct vertices of G is called the total vertex irregularity strength of this graph, and is denoted by . We prove that for each graph of order n and with minimum degree δ>0. 相似文献
7.
For a fixed multigraph H with vertices w1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d′ such that every n-vertex graph with minimum degree at least d′ is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H. 相似文献
8.
Alfredo García Ferran Hurtado Clemens Huemer Javier Tejel Pavel Valtr 《Computational Geometry》2009,42(9):913-922
Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. 相似文献
9.
The transformation graph G-+- of a graph G is the graph with vertex set V(G)E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: (i) u,vV(G) and they are not adjacent in G, (ii) u,vE(G) and they are adjacent in G, (iii) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. In this paper, for any graph G, we determine the connectivity and the independence number of G-+-. Furthermore, for a graph G of order n4, we show that G-+- is hamiltonian if and only if G is not isomorphic to any graph in {2K1+K2,K1+K3}{K1,n-1,K1,n-1+e,K1,n-2+K1}. 相似文献
10.
Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK2 a matching of size m and as Bn,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GBn,k, rb(G,mK2)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles. 相似文献
11.
Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ2(G)n+k-1. Let v1,…,vk be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C1,…,Ck with viV(Ci) for all 1ik.Then G has k vertex-disjoint cycles such that
- (i) for all 1ik.
- (ii) , and
- (iii) At least k-1 of the k cycles are triangles.
Keywords: Degree sum condition; Independent vertices; Vertex-disjoint cycles 相似文献
12.
In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=Kk(K1+Kn−k−1), the join of Kk, the complete graph on k vertices, with the disjoint union of K1 and Kn−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum. 相似文献
13.
We consider the diameter of a random graph G(n, p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n, p) is close to
if np → ∞. Moreover if
, then the diameter of G(n, p) is concentrated on two values. In general, if
, the diameter is concentrated on at most 21/c0 + 4 values. We also proved that the diameter of G(n, p) is almost surely equal to the diameter of its giant component if np > 3.6. 相似文献
14.
Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by dG(S) or d(S). The Steiner n-eccentricity en(v) and Steiner n-distance dn(v) of a vertex v in G are defined as en(v)=max{d(S)| SV(G), |S|=n and vS} and dn(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center Cn(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median Mn(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that Cn(T) is contained in Cn+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that Mn(T) is contained in Mn+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which Cn(G)Cn+1(G). We also show that for each n2 there is a distance–hereditary graph G such that Mn(G)Mn+1(G). Despite these negative examples, we prove that if G is a block graph then Mn(G) is contained in Mn+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described. 相似文献
15.
A graph G is (m,n)-linked if for any two disjoint subsets R,BV(G) with |R|m and |B|n, G has two disjoint connected subgraphs containing R and B, respectively. We shall prove that a planar graph with at least six vertices is (3,3)-linked if and only if G is 4-connected and maximal. 相似文献
16.
Cheng-Kuan Lin Jimmy J.M. Tan Hua-Min Huang D. Frank Hsu Lih-Hsing Hsu 《Discrete Mathematics》2009,309(17):5474-5483
A hamiltonian cycle C of a graph G is an ordered set u1,u2,…,un(G),u1 of vertices such that ui≠uj for i≠j and ui is adjacent to ui+1 for every i{1,2,…,n(G)−1} and un(G) is adjacent to u1, where n(G) is the order of G. The vertex u1 is the starting vertex and ui is the ith vertex of C. Two hamiltonian cycles C1=u1,u2,…,un(G),u1 and C2=v1,v2,…,vn(G),v1 of G are independent if u1=v1 and ui≠vi for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C1,C2,…,Ck} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs Pn and the n-dimensional star graphs Sn. It is proven that IHC(P3)=1, IHC(Pn)=n−1 if n≥4, IHC(Sn)=n−2 if n{3,4} and IHC(Sn)=n−1 if n≥5. 相似文献
17.
Marcelo H. de Carvalho Cludio L. Lucchesi U.S.R. Murty 《Journal of Combinatorial Theory, Series B》2004,92(2):319-324
The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in QE belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x0 (non-negativity), (ii) x(∂(v))=1, for all vV (degree constraints) and (iii) x(∂(S))1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi. 相似文献
18.
Guantao Chen Yuan Chen Shuhong Gao Zhiquan Hu 《Journal of Combinatorial Theory, Series B》2008,98(4):735-751
A graph G is k-linked if G has at least 2k vertices, and for every sequence x1,x2,…,xk,y1,y2,…,yk of distinct vertices, G contains k vertex-disjoint paths P1,P2,…,Pk such that Pi joins xi and yi for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m1,m2,…,mk)-linked if, in addition, for any k-tuple (d1,d2,…,dk) of natural numbers, the paths P1,P2,…,Pk can be chosen such that Pi has length di modulo mi for i=1,2,…,k. Thomassen showed that, for each k-tuple (m1,m2,…,mk) of odd positive integers, there exists a natural number f(m1,m2,…,mk) such that every f(m1,m2,…,mk)-connected graph is modulo (m1,m2,…,mk)-linked. For m1=m2=…=mk=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo (2,2,…,2)-linked or there is XV(G) such that |X|4k−3 and G−X is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m1,m2,…,mk)max{14(m1+m2++mk)−4k,6(m1+m2++mk)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some mi be even integers. Let (m1,m2,…,mk) be a k-tuple of natural numbers and ℓk such that mi is odd for each i with ℓ+1ik. If G is 45(m1+m2++mk)-connected, then either G has a vertex set X of order at most 2k+2ℓ−3+δ(m1,…,mℓ) such that G−X is bipartite or G is modulo (2m1,…,2mℓ,mℓ+1,…,mk)-linked, where Our results generalize several known results on parity-linked graphs. 相似文献
19.
Given a graph G=(V,E) with strictly positive integer weights ωi on the vertices iV, a k-interval coloring of G is a function I that assigns an interval I(i){1,…,k} of ωi consecutive integers (called colors) to each vertex iV. If two adjacent vertices x and y have common colors, i.e. I(i)∩I(j)≠0/ for an edge [i,j] in G, then the edge [i,j] is said conflicting. A k-interval coloring without conflicting edges is said legal. The interval coloring problem (ICP) is to determine the smallest integer k, called interval chromatic number of G and denoted χint(G), such that there exists a legal k-interval coloring of G. For a fixed integer k, the k-interval graph coloring problem (k-ICP) is to determine a k-interval coloring of G with a minimum number of conflicting edges. The ICP and k-ICP generalize classical vertex coloring problems where a single color has to be assigned to each vertex (i.e., ωi=1 for all vertices iV).Two k-interval colorings I1 and I2 are said equivalent if there is a permutation π of the integers 1,…,k such that ℓI1(i) if and only if π(ℓ)I2(i) for all vertices iV. As for classical vertex coloring, the efficiency of algorithms that solve the ICP or the k-ICP can be increased by avoiding considering equivalent k-interval colorings, assuming that they can be identified very quickly. To this purpose, we define and prove a necessary and sufficient condition for the equivalence of two k-interval colorings. We then show how a simple tabu search algorithm for the k-ICP can possibly be improved by forbidding the visit of equivalent solutions. 相似文献
20.
In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}. 相似文献