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.     

On the 2-factor index of a graph

The 2-factor index of a graph G, denoted by f(G), is the smallest integer m such that the m-iterated line graph L^m(G) of G contains a 2-factor. In this paper, we provide a formula for f(G), and point out that there is a polynomial time algorithm to determine f(G).     

The codiameter of a 2-connected graph

The codiameter of a graph is defined as the minimum, taken over all pairs of vertices u and v in the graph, of the maximum length of a (u,v)-path. A result of Fan [Long cycles and the codiameter of a graph, I, J. Combin. Theory Ser. B 49 (1990) 151-180.] is that, for an integer c?3, if G is a 2-connected graph on n vertices with more than ((c+1)/2)(n-2)+1 edges, the codiameter of G is at least c. The result is best possible when n-2 is divisible by c-2. In this paper, we shall show that the bound ((c+1)/2)(n-2)+1 can be decreased when n-2 is not divisible by c-2.     

Edges not contained in triangles and the number of contractible edges in a 4-connected graph

Let G be a 4-connected graph, and let E_c(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have .     

Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph

We prove results concerning the distribution of 4-contractible edges in a 4-connected graph G in connection with the edges of G not contained in a triangle. As a corollary, we show that if G is 4-regular 4-connected graph, then the number of 4-contractible edges of G is at least one half of the number of edges of G not contained in a triangle.     

Sharply transitive 1-factorizations of the complete graph with an invariant 1-factor

We give some simple characterizations of those n for which K_n has a sharply transitive 1-factorization with an assigned automorphism group that acts sharply transitively on the vertex set and also fixes a 1-factor. © 1994 John Wiley & Sons, Inc.     

On the Euler genus of a 2-connected graph

The Euler genus of the surface Σ obtained from the sphere by the addition of k crosscaps and h handles is ε(Σ) = k + 2h. For a graph G, the Euler genus ε(G) of G is the smallest Euler genus among all surfaces in which G embeds. The following additivity theorem is proved.Theorem. Suppose G = H ∪ K, where H and K have exactly the vertices v and win common. Then ε(G) = min(ε(H + vw) + ε(K + vw), ε(H) + ε(K) + 2).     

On the non-orientable genus of a 2-connected graph

In earlier works, additivity theorems for the genus and Euler genus of unions of graphs at two points have been given. In this work, the analogous result for the non-orientable genus is given. If Σ is obtained from the sphere by the addition of k>0 crosscaps, define γ(Σ) to be k. For a graph G, define γ(G) to be the least element in the set {γ(Σ) | G embeds in Σ}.Theorem. Let H₁ and H₂ be connected graphs such that H₁ ∩ H₂ consists of the isolated vertices v and w. Then, for some μ ϵ −1, 0, 1, 2, γ(H₁ ∪ H₂) = γ(H₁) + γ(H₂) + μ.A formula for μ is given.     

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor.     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?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).     

The maximum number of edges in a minimal graph of diameter 2

A graph g of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for n < n_o. If g has n vertices then it has at most n²/4 edges. The only extremum is the complete bipartite graph.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.