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.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

[2,3]-factors in a 3-connected infinite planar graph

For two integersm, n withm<-n, an[m, n]-factorF in a graphG is a spanning subgraph ofG withm<-d _F (v)<-n for allv∈V(F). In 1996, H. Enomoto et al. proved that every 3-connected planar graphG withd _G (v)>-4 for allv∈V(G) contains a [2,3]-factor. In this paper we extend their result to all 3-connected locally finite infinite planar graphs containing no unbounded faces.     

Long Cycles Generate the Cycle Space of a Graph

Let G be a 2-connected graph in which the degree of every vertex is at least d. We prove that the cycles of length at least d + 1 generate the cycle space of G, unless G ≌ K_d+1 and d is odd. As a corollary, we deduce that the cycles of length at least d + 1 generate the subspace of even cycles in G. We also establish the existence of odd cycles of length at least d + 1 in the case when G is not bipartite.A second result states: if G is 2-connected with chromatic number at least k, then the cycles of length at least k generate the cycle space of G, unless G ≌ K_k and k is even. Similar corollaries follow, among them a stronger version of a theorem of Erdös and Hajnal.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

Uniqueness and faithfulness of embedding of toroidal graphs

A topological generalization of the uniqueness of duals of 3-connected planar graphs will be obtained. A graph G is uniquely embeddable in a surface F if for any two embeddings $\text{?}{}_1$, $\text{?}{}_2\text{:G → F}$, there are an autohomeomorphism h:F → F and an automorphism σ:G → G such that $\text{h°?}{}_1\text{= ?}{}_2\text{°σ}$. A graph G is faithfully embedabble in a surface F if there is an embedding $\text{?:G → F}$ such that for any automorphism σ:G → G, there is an autohomeomorphism h:F → F with $\text{h°? = f°σ}$. Our main theorems state that any 6-connected toroidal graph is uniquelly embeddable in a torus and that any 6-connected toroidal graph with precisely three exceptions is faithfully embeddable in a torus. The proofs are based on a classification of 6-regular torus graphs.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

Bounds on the number of cycles of length three in a planar graph

LetG be ap-vertex planar graph having a representation in the plane with nontriangular facesF ₁,F ₂, …,F _r. Letf ₁,f ₂, …,f _r denote the lengths of the cycles bounding the facesF ₁,F ₂, …,F _r respectively. LetC ₃(G) be the number of cycles of length three inG. We give bounds onC ₃(G) in terms ofp,f ₁,f ₂, …,f _r. WhenG is 3-connected these bounds are bounds for the number of triangles in a polyhedron. We also show that all possible values ofC ₃(G) between the maximum and minimum value are actually achieved. This research was supported in part by the U.S.A.F. Office of Scientific Research, Systems Command, under Grant AFOSR-76-3017 and the National Science Foundation under Grant ENG79-09724.     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.     

Contractible edges in some k-connected graphs

An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K ₁ + (K ₂ ∪ K _1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K ₁ + (K ₂ ∪ K _1,t ), nor K ₁ + (2K ₂ ∪ K _1,2), then G has a k-contractible edge.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

The 2-extendability of 5-connected graphs on surfaces with large representativity

A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F², except the sphere, is 2-extendable if ρ(G)?7−2χ(F²), where ρ(G) stands for the representativity of G on F² and χ(F²) for the Euler characteristic of F².     

The maximum corank of graphs with a 2-separation

For a graph G=(V,E) with vertex-set V={1,2,…,n}, which is allowed to have parallel edges, and for a field F, let S(G;F) be the set of all F-valued symmetric n×n matrices A which represent G. The maximum corank of a graph G is the maximum possible corank over all A∈S(G;F). If (G₁,G₂) is a (?2)-separation, we give a formula which relates the maximum corank of G to the maximum corank of some small variations of G₁ and G₂.     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least ${\frac{1}{2}|G|}$ vertices of degree 5.     

On the sum of powers of terms of a linear recurrence sequence

Let (F _n ) _n??0 be the Fibonacci sequence given by F _n+2 = F _n+1 + F _n , for n ?? 0, where F ₀ = 0 and F ₁ = 1. There are several interesting identities involving this sequence such as F _n ² + F _n+1 ² = F _2n+1, for all n ?? 0. In a very recent paper, Marques and Togbé proved that if F _n ^s + F _n+1 ^s is a Fibonacci number for all sufficiently large n, then s = 1 or 2. In this paper, we will prove, in particular, that if (G _m ) _m is a linear recurrence sequence (under weak assumptions) and G _n ^s + ... + G _n+k ^s ?? (G _m ) _m , for infinitely many positive integers n, then s is bounded by an effectively computable constant depending only on k and the parameters of G _m .     

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.