Vertex pancyclicity in quasi claw-free graphs

This paper generalizes the concept of locally connected graphs. A graph G is triangularly connected if for every pair of edges e₁,e₂∈E(G), G has a sequence of 3-cycles C₁,C₂,…,C_l such that e₁∈C₁,e₂∈C_l and E(C_i)∩E(C_i+1)≠∅ for 1?i?l-1. In this paper, we show that every triangularly connected quasi claw-free graph on at least three vertices is vertex pancyclic. Therefore, the conjecture proposed by Ainouche is solved.     

Every 3-connected,locally connected,claw-free graph is Hamilton-connected

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of order p ≥ 4, containing no induced subgraph isomorphic to K_1,3, is Hamilton-connected if and only if G is 3-connected. © 1996 John Wiley & Sons, Inc.     

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.     

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.     

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.     

On hamiltonicity of 2-connected claw-free graphs

A graph G has the hourglass property if every induced hourglass S (a tree with a degree sequence 22224) contains two non-adjacent vertices which have a common neighbor in G - V(S).For an integer k ≥ 4,...     

The Hamiltonian index of graphs

The Hamiltonian index of a graph G is defined as

h(G)=min{m:L^m(G) is Hamiltonian}.     

On the distance function of a connected graph

An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].     

Hamiltonicity of 6-connected line graphs

Let G be a graph and let D₆(G)={v∈V(G)|d_G(v)=6}. In this paper we prove that: (i) If G is a 6-connected claw-free graph and if |D₆(G)|≤74 or G[D₆(G)] contains at most 8 vertex disjoint K₄’s, then G is Hamiltonian; (ii) If G is a 6-connected line graph and if |D₆(G)|≤54 or G[D₆(G)] contains at most 5 vertex disjoint K₄’s, then G is Hamilton-connected.     

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.     

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.     

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean

Zeta functions and complexities of a semiregular bipartite graph and its line graph

We treat zeta functions and complexities of semiregular bipartite graphs. Furthermore, we give formulas for zeta function and the complexity of a line graph of a semiregular bipartite graph. As a corollary, we present the complexity of a line graph of a complete bipartite graph.     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

Every connected regular graph of even degree is a Schreier coset graph

Using Petersen's theorem, that every regular graph of even degree is 2-factorable, it is proved that every connected regular graph of even degree is isomorphic to a Schreier coset graph. The method used is a special application of the permutation voltage graph construction developed by the author and Tucker. This work is related to graph imbedding theory, because a Schreier coset graph is a covering space of a bouquet of circles.     

On the doubly connected domination number of a graph

For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.     

Every signed planar graph without cycles of length from 4 to 8 is 3-colorable

In this paper, we investigate the signed graph version of Erdös problem: Is there a constant $c$ such that every signed planar graph without $k$-cycles, where $4\le k\le c$, is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$