language-icon Old Web
English
Sign In

Panconnected index of graphs

2017 
For a connected graph G not isomorphic to a path, a cycle or a K1,3, let pc(G) denote the smallest integer n such that the nth iterated line graph Ln(G) is panconnected. A path P is a divalent path of G if the internal vertices of P are of degree 2 in G. If every edge of P is a cut edge of G, then P is a bridge divalent path of G; if the two ends of P are of degree s and t, respectively, then P is called a divalent(s,t)-path. Let (G)=max{m:G has a divalent path of length m that is not both of length 2 and in a K3}. We prove the following.(i) If G is a connected triangular graph, then L(G) is panconnected if and only if G is essentially 3-edge-connected.(ii) pc(G)(G)+2. Furthermore, if (G)2, then pc(G)=(G)+2 if and only if for some integer t3, G has a bridge divalent (3,t)-path of length (G).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    20
    References
    2
    Citations
    NaN
    KQI
    []