zbMATH — the first resource for mathematics

Hamiltonian-like indices of graphs. (English) Zbl 0536.05046
A graph G is said to be m-triangular if each edge of G is in at least m- triangles. The authors establish the following results: Theorem 1. If G is connected and 2-triangular, then L(G) is panconnected; Theorem 2. If G is 2-connected and 1-triangular, then L(G) is panconnected. The P index P(G) of a graph is the minimum k such that the k-th interated line graph of G has property P. Let h, p, vp, ep, eh, hc and pc denote the poperties hamiltonian, pancyclic, vertex-pancyclic, edge-pancyclic, edge- hamiltonian, hamiltonian-connected and panconnected, respectively.
As consequences of Theorems 1 and 2 are: a) If G is a connected graph with minimum degree three and G contains a bridge incident with a vertex of degree three then \(eh(G)=ep(G)=hc(G)=pc(G)=3\); b) If G is a graph with minimum degree at least three and edge-connectivity two, then \(hc(G)=pc(G)=2\); c) If G is a connected graph which is neither a path nor a cycle, then P(G) is finite for all \(P\in \{h,\quad p,\quad vp,\quad ep,\quad eh,\quad hc,\quad pc\}.\) Let \(P\in \{h,\quad p,\quad vp,\quad ep,\quad eh,\quad hc,\quad pc\}.\) The authors use Theorems 1 and 2 to determine the exact value of P(T) if T is a tree, and to obtain sharp bounds on P(G) as a function of the connectivity and minimum degree of a graph G. (The same title with a wrong review appeared in Zbl 0515.05041.)
Reviewer: L.Lesniak

05C45 Eulerian and Hamiltonian graphs