Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

The circular chromatic number of series‐parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K₄‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K₅‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

Hamiltonicity for K1, r-free graphs

In this paper, we investigate the Hamiltonicity of K_1,r-free graphs with some degree conditions. In particular, let G be a k-connected grph of order n≧3 which is K_1,4-free. If for every independent set {v₀, v₁, …, v_k} then G is hamiltonian. We use an upper bound for the independence number of K_1,r-free graphs to extent the above result to K_1,r-free graphs. Hamiltonian connected and, more generally, q-edge hamiltonian properties are studied here as well. © 1995 John Wiley & Sons, Inc.     

Maximum chromatic polynomials of 2-connected graphs

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 C_n 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 ≠ C_n} 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.     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex-transitive graphs. © 1995 John Wiley & Sons, Inc.     

A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity

Sumner [7] proved that every connected K _1,3-free graph of even order has a perfect matching. He also considered graphs of higher connectivity and proved that if m ≥ 2, every m-connected K _1,m+1-free graph of even order has a perfect matching. In [6], two of the present authors obtained a converse of sorts to Sumner’s result by asking what single graph one can forbid to force the existence of a perfect matching in an m-connected graph of even order and proved that a star is the only possibility. In [2], Fujita et al. extended this work by considering pairs of forbidden subgraphs which force the existence of a perfect matching in a connected graph of even order. But they did not settle the same problem for graphs of higher connectivity. In this paper, we give an answer to this problem. Together with the result in [2], a complete characterization of the pairs is given.     

Decomposition of 3-connected graphs

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.     

A Classification of Fully Residually Free Groups of Rank Three or Less

A groupGisfully residually freeprovided to every finite setS ⊂ G\{1} of non-trivial elements ofGthere is a free groupF_Sand an epimorphismh_S:G → F_Ssuch thath_S(g) ≠ 1 for allg ∈ S. Ifnis a positive integer, then a groupGisn-freeprovided every subgroup ofGgenerated bynor fewer distinct elements is free. Our main result shows that a fully residually free group of rank at most 3 is either abelian, free, or a free rank one extension of centralizers of a rank two free group. To prove this we prove that every 2-free, fully residually free group is actually 3-free. There are fully residually free groups which are not 2-free and there are 3-free, fully residually free groups which are not 4-free.     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

Forbidden induced subgraphs for star-free graphs

Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K_1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.     

Regular factors in K1,3-free graphs

We show that every connected K_1,3-free graph with minimum degree at least 2k contains a k-factor and construct connected K_1,3-free graphs with minimum degree k + 0(√k) that have no k-factor.     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

Generating planar 4-connected graphs

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 ₀,G ₁, …,G _n such thatG ₀ 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.     

A necessary and sufficient condition for connected,locally k-connected k1,3-free graphs to be k-hamiltonian

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K_1,3-free graph is k-hamiltonian if and only if it is (k + 2)-connected (K ? 1).     

Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

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).     

Degree-Light-Free Graphs and Hamiltonian Cycles

 Let G and H be graphs. G is said to be degree-light H-free if G is either H-free or, for every induced subgraph K of G with K≅H, and every {u,v}⊆K, d i s t _K (u,v)=2 implies max {d(u),d(v)}≥|V(G)|/2. In this paper, we will show that every 2-connected graph with either degree-light {K _1,3, P ₆}-free or degree-light {K _1,3, Z}-free is hamiltonian (with three exceptional graphs), where P ₆ is a path of order 6 and Z is obtained from P ₆ by adding an edge between the first and the third vertex of P ₆ (see Figure 1). Received: December 9, 1998?Final version received: July 21, 1999     

On the sum of all distances in chromatic blocks

In this paper all 2-connected k-chromatic graphs of order n with the maximum sum of all distances between their vertices are characterized for every k ≥ 2, thus strengthening a result of J. Plesnik. Moreover, several auxiliary results are proved on chromatic critical graphs and 2-connected graphs.     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.