Note on non-separating and removable cycles in highly connected graphs

We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense.     

Upon the removal of the edges of a 1-factor from an even circuit in a 2-connected graph

Let G be a 2-connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G with factorization F={F₁,F₂} such that G−E(F₁) is 2-connected.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

Circuit double covers in special types of cubic graphs

Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.     

Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.     

A weaker version of Lovász' path removal conjecture

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.     

On the connectivity and superconnected graphs with small diameter

In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.     

Packing edge-disjoint cycles in graphs and the cyclomatic number

For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly.     

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

Circuit preserving edge maps

It is proved that any one-to-one edge map f from a 3-connected graph G onto a graph G′, G and G′ possibly infinite, satisfying f(C) is a circuit in G′ whenever C is a circuit in G is induced by a vertex isomorphism. This generalizes a result of Whitney which hypothesizes f(C) is a circuit in G′ if and only if C is a circuit in G.     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

Even cycles in graphs

Let G be a 3‐connected simple graph of minimum degree 4 on at least six vertices. The author proves the existence of an even cycle C in G such that G‐V(C) is connected and G‐E(C) is 2‐connected. The result is related to previous results of Jackson, and Thomassen and Toft. Thomassen and Toft proved that G contains an induced cycle C such that both G‐V(C) and G‐E(C) is 2‐connected. G does not in general contain an even cycle such that G‐V(C) is 2‐connected. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 163–223, 2004     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

5-Shredders in 5-connected graphs

For a graph G, a subset S of V(G) is called a shredder if G−S consists of three or more components. We show that if G is a 5-connected graph with |V(G)|≥135, then the number of shredders of cardinality 5 of G is less than or equal to (2|V(G)|−10)/3.     

Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

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.     

Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete

Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293-299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.