共查询到20条相似文献,搜索用时 31 毫秒
1.
Ioan Tomescu 《Journal of Graph Theory》1994,18(4):329-336
In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles Cn and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ Cn} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having X(G) = 2 and X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined. 相似文献
2.
Kara Lee Walcher 《Journal of Graph Theory》1996,23(4):355-360
Let G be a graph on p vertices. Then for a positive integer n1 G is said to be n-extendible if (i) n < p/2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is n-connected, then Gk is -extendible for every integer k ≥ 2 such that . © 1996 John Wiley & Sons, Inc. 相似文献
3.
A graphG having a 1-factor is calledn-extendible if every matching of sizen extends to a 1-factor. LetG be a 2-connected graph of order 2p. Letr0 andn>0 be integers such thatp–rn+1. It is shown that ifG/S isn-extendible for every connected subgraphS of order 2r for whichG/S is connected, thenG isn-extendible. 相似文献
4.
David Barnette 《Israel Journal of Mathematics》1973,14(1):1-13
In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision
of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these
three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG
0,G
1, …,G
n such thatG
0 is the graph of the cube,G
n=G, and each graph is obtained from its predecessor by one of our three operations.
Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963. 相似文献
5.
Let G be a graph of order n ? 3. We prove that if G is k-connected (k ? 2) and the degree sum of k + 1 mutually independent vertices of G is greater than 1/3(k + 1)(n + 1), then the line graph L(G) of G is pancyclic. We also prove that if G is such that the degree sum of every 2 adjacent vertices is at least n, then L(G) is panconnected with some exceptions. 相似文献
6.
Július Czap 《Discrete Mathematics》2011,311(21):2570
A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χp(G).In this paper we prove that χp(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χp(G)=10. If a 2-connected outerplane graph G is bipartite, then χp(G)≤8, moreover, this bound is best possible. 相似文献
7.
Mekkia Kouider 《Combinatorica》2000,20(2):219-226
G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle.
This result will be in fact generalised by considering tuples instead of pairs of vertices.
Let be the minimum degree in the induced graph <X>. For any ,
.
If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient.
So we deduce the following:
Let p and t () be two integers.
Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G.
If furthermore , (p-1) cycles are sufficient.
In particular, if and , then G is hamiltonian.
Received April 3, 1998 相似文献
8.
Let G be a group with a dihedral subgroup H of order 2pn, where p is an odd prime. We show that if there exist H-connected transversals in G, then G is a solvable group. We apply this result to the loop theory and show that if the inner mapping group of a finite loop Q is dihedral of order 2pn, then Q is a solvable loop.1991 Mathematics Subject Classification: 20D10, 20N05 相似文献
9.
A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K1,3 is panconnected. 相似文献
10.
A point disconnecting set S of a graph G is a nontrivial m-separator, where m = |S|, if the connected components of G - S can be partitioned into two subgraphs, each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial 3-separators. Suppose G is a graph having n ≥ 6 points. We prove three results: (1) If G is quasi 4-connected with at least 3n - 4 edges, then the graph K?1, obtained from K6 by deleting an edge, is a minor of G. (2) If G has at least 3n - 4 edges then either K?6 or the graph obtained by pasting two disjoint copies of K5 together along a triangle is a minor of G. (3) If the minimum degree of G is at least 6, then K?6 is a minor of G. © 1993 John Wiley & Sons, Inc. 相似文献
11.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
12.
It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected. 相似文献
13.
K. Truemper 《Journal of Graph Theory》1980,4(1):43-49
Let G and H be 2-connected 2-isomorphic graphs with n nodes. Whitney's 2-isomorphism theorem states that G may be transformed to a graph G* isomorphic to H by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitney's theorem that is much shorter than the original one, using a graph decomposition by Tutte. The proof also establishes a surprisingly small upper bound, namely n-2, on the minimal number of switchings required to derive G* from G. The bound is sharp in the sense that for any integer N there exist graphs G and H with n ≥ N nodes for which the minimal number of switchings is n-2. 相似文献
14.
Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βnα for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc. 相似文献
15.
In this paper, we show that n ? 4 and if G is a 2-connected graph with 2n or 2n?1 vertices which is regular of degree n?2, then G is Hamiltonian if and only if G is not the Petersen graph. 相似文献
16.
Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K
3,n
for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University. 相似文献
17.
The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G−v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least 3k/2+2. Then G has an edge e such that G−V(e) is still k-connected.The bound on the minimum degree is essentially best possible. 相似文献
18.
A well-known result of Dirac (Math. Nachr. 22 (1960) 61) says that given n vertices in an n-connected G, G has a cycle through all of them. In this paper, we generalize Dirac's result as follows:Given at most
vertices in an n-connected graph G when n3 and
, then G has a cycle through exactly n vertices of them.This improves the previous known bound given by Kaneko and Saito (J. Graph Theory 15(6) (1991) 655). 相似文献
19.
A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χp(G).In this paper, we prove that χp(G)≤118 for every 2-connected plane graph G. 相似文献
20.
Eden Y. Woon 《Israel Journal of Mathematics》1985,52(3):177-192
A graph is a 1-dimensional simplicial complex. In this work we study an interpretation of “n-connectedness” for 2-dimensional simplicial complexes. We prove a 2-dimensional analogue of a theorem by Whitney for graphs:
Theorem (A Whitney type theorem for pure 2-complexes).Let G be a pure 2-complex with no end-triangles. Then G is n-connected if and only if the valence of e is at least n for every interior edge
e of G, and there does not exist a juncture set J of less than n edges of G.
Examples ofn-connected pure 2-complexes are then given, and some consequences are proved. 相似文献